배열의 응용 : 희소 행렬 / 전치행렬

희소 행렬이란? 행렬의 값이 대부분 0인 행렬

일반적으로 행렬은 2차원 배열을 이용한다.

#define MAX_ROWS 100
#define MAX_COLS 100

int matrix[MAX_ROWS][MAX_COLS];

이것이 방법 1 이고.

하지만, 이 방법으로 행렬을 표현하게 된다면 다수의 항이 0일 경우에 메모리 낭비가 심하게 된다.

그래서 다른 방법을 사용할 필요가 있다.

---

희소 행렬을 나타내는 다른 방법

배열을 이용하되 행렬 값이 0이 아닌 노드만을 행 / 열 / 값 으로 표시하는 것이다.

이것이 방법 2 이다.

예를 들어,

이렇게 생긴 행렬이 있다고 가정해보자.

이 행렬을 새로운 방법으로 나타내면,

이렇게 나타낼 수 있다.

---

만약 방법 1(이차원 배열)로 행렬의 전치 연산을 한다고 생각해보자.

방법 1에서는 (i, j)의 요소와 (j, i)의 요소를 교환해주기만 하면 된다.

---

방법 1로 전치행렬 계산

#include <stdio.h>
#include <stdlib.h>

#define ROWS 3
#define COLS 3

//행렬 교환
void TransposMatrix(int A[ROWS][COLS], int B[ROWS][COLS]) {
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            B[j][i] = A[i][j]; //행렬 값 교환
        }
    }
}

//행렬 출력
void PrintMatrix(int A[ROWS][COLS]) {
    printf("=================\n");
    for(int i = 0; i < ROWS; i++) {
        for(int j = 0; j < COLS; j++) {
            printf("%d ", A[i][j]);
        }
        printf("\n");
    }
}

int main(void) {
    int array1[ROWS][COLS] = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
    };

    int array2[ROWS][COLS];

    TransposMatrix(array1, array2);
    PrintMatrix(array1);
    PrintMatrix(array2);

    return 0;
}

---

방법 2로 전치행렬 계산

방법 2로 전치행렬을 계산한다면, 일단 기존에 있던 배열을 A / 전치 연산한 배열을 B라고 해보자

이렇게 변경해주면 된다.

주의할 점

전치 연산을 하기 전에, 기존 방법 2에서는 행의 순서대로 저장되었다. ex) 행이 0 -> 행이 1 -> 행이 1 이 순서대로 저장되었음.

하지만, 위처럼 단순히 행값과 열값을 바꾼다면 행의 순서대로 저장되지 않는다. ex) 행이 3 -> 행이 0 -> 행이 5 순서가 맞지 않는다.

 

즉, B를 

이런 순서로 저장되게 해야한다.

어떻게 해야할까?

 

방법은 이렇다.

어떤 변수를 i = 0이라고 선언한다.

우선 A에서의 열이 B에서의 행이 되므로,

i = 0을 증가시키면서, A의 열값과 비교한다.

만약 i와 A의 열값이 동일하다면 교환 후, 저장하면 된다. (순서대로 저장되게 된다.)

---

코드를 보면서 확인해보자.

#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 100

typedef struct {
    int row; //행
    int col; //열
    int value; //값
} element;

방법 2는, 행렬의 값이 0이 아닌 항을 '행/열/값' 으로 나타내는 방법이라고 하였다.

그러므로 element라는 구조체에 행, 열, 값을 가질 수 있는 변수를 만들어 준다.

 

typedef struct {
    element data[MAX_TERMS];

    int rows; //행의 개수
    int cols; //열의 개수
    int terms; //항의 개수
} SparseMatrix;

전치된 행렬을 담을 구조체를 정의한다.

 

이런식으로 하려고

즉, 하나의 element구조체(요소)여러개를 data배열안에 넣기 위해서 위처럼 코드 만들었음.

 

 

SparseMatrix TransposMatrix(SparseMatrix a) {
    SparseMatrix b;

    int bindex; //행렬 b에서 현재 저장 위치
    b.rows = a.cols; //a의 열의 개수는 b의 행의 개수가 될 것임
    b.cols = a.rows; //a의 행의 개수는 b의 열의 개수가 될 것임
    b.terms = a.terms; //항의 개수를 동일

    if(a.terms > 0) {
        bindex = 0;
        for(int i = 0; i < b.rows; i++) { //열을 낮은 것부터 높은 순서로 배열해야함
            for(int j = 0; j < a.terms; j++) {
                if(a.data[j].col == i) { //i = 0부터 증가되면서 i와 일치하는 전치되기전의 열이
                                         //있다면, 교환하고 저장 (이부분이 순서대로 저장되는 부분)
                    b.data[bindex].row = a.data[j].col;
                    b.data[bindex].col = a.data[j].row;
                    b.data[bindex].value = a.data[j].value;
                    bindex++;
                }
            }
        }
    }
    return b;
}

이 부분에서 전치가 이뤄진다.

 

전체적인 코드를 살펴보자.

#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 100

typedef struct {
    int row; //행
    int col; //열
    int value; //값
} element;

typedef struct {
    element data[MAX_TERMS];

    int rows; //행의 개수
    int cols; //열의 개수
    int terms; //항의 개수
} SparseMatrix;

SparseMatrix TransposMatrix(SparseMatrix a) {
    SparseMatrix b;

    int bindex; //행렬 b에서 현재 저장 위치
    b.rows = a.cols; //a의 열의 개수는 b의 행의 개수가 될 것임
    b.cols = a.rows; //a의 행의 개수는 b의 열의 개수가 될 것임
    b.terms = a.terms; //항의 개수를 동일

    if(a.terms > 0) {
        bindex = 0;
        for(int i = 0; i < b.rows; i++) { //열을 낮은 것부터 높은 순서로 배열해야함
            for(int j = 0; j < a.terms; j++) {
                if(a.data[j].col == i) {
                    b.data[bindex].row = a.data[j].col;
                    b.data[bindex].col = a.data[j].row;
                    b.data[bindex].value = a.data[j].value;
                    bindex++;
                }
            }
        }
    }
    return b;
}

void PrintSparseMatrix(SparseMatrix a) {
    printf("=====================\n");
    for(int i = 0; i < a.terms; i++) {
        printf("(%d %d %d)\n", a.data[i].row, a.data[i].col, a.data[i].value);
    }
    printf("=====================\n");
}

int main(void) {
    SparseMatrix m = {
            {{0, 3, 7}, {1, 0, 9}, {1, 5, 8},
             {3, 0, 6}, {3, 1, 5}, {4, 5, 1},
             {5, 2, 2}},
             6,
             6,
             7
    };

    SparseMatrix result;
    result = TransposMatrix(m);
    PrintSparseMatrix(result);

    return 0;
}

 

 

(0, 3, 7)

(1, 0, 9)

(1, 5, 8)

(3, 0, 6)

(3, 1, 5)

(4, 5, 1)

(5, 2, 2)

를 전치연산 한 결과는?

 

실행 결과)