17. 희소행렬

희소행렬이란?

희소행렬이란 행렬 중에서 대부분의 원소가 0으로 이루어진 행렬을 의미한다. 이러한 행렬은 2차원 배열로 표현하기에는 비효율적이므로 효율적으로 표현하고 연산을 수행하기 위해 희소행렬 표현방법이 사용된다. 희소행렬을 표현할 때에는 0이 아닌 원소들만 저장하는 방식으로 표현된다.

---

희소행렬 표현

희소행렬을 표현할 때에는 표현할 원소의 행 인덱스, 열 인덱스, 원소 값을 한 번에 표현한다.

typedef struct{
    int row;
    int col;
    int value;
}term;

행, 열, 원소 값을 한번에 저장하기 위해 구조체를 이용하여 값을 저장한다.

---

희소행렬의 전치

희소행렬의 예시와 표현방법 전치된 값을 보면 아래와 같다.

희소행렬	희소행렬 표현법	희소행렬 전치
15   0    0   22   0   -15  0   11   3    0    0    0  0    0    0   -6    0    0 91   0    0    0    0    0  0    0   28   0    0    0	행     열     값     [0]      6       6       8     [1]      0       0      15     [2]      0       3      22     [3]      0       5     -15     [4]      1       1      11     [5]      1       2       3     [6]      2       3      -6     [7]      4       0      91     [8]      5       2      28	행     열     값     [0]      6       6       8     [1]      0       0      15     [2]      0       4      91     [3]      1       1      11     [4]      2       1       3     [5]      2       5      28     [6]      3       0      22     [7]      3       2      -6     [8]      5       0     -15

0 인덱스에는 행렬의 행 크기, 열 크기, 0이 아닌 원소의 수가 저장되며, 1 인덱스부터는 실제 원소가 저장된 행, 열, 값이 저장된다.  전치된 행렬은 행과 열을 뒤바꿔서 저장하면 된다. 하지만 행으로 올림차순 정렬이 되어 있다는 것을 의식해야 한다.

---

Transpose 알고리즘

가장 기본적으로 희소행렬을 전치하는 알고리즘이다.

void Transpose(term a[], term b[]){
    int i, j, n, current;
    n = a[0].value;
    b[0].row = a[0].col;
    b[0].col = a[0].row;
    b[0].value = n;
    
    if(n){
        current = 1;
        for(i=0; i<a[0].col; i++){
            for(j=0;j<=n;j++){
                if(a[j].col == i){
                    b[current].row = a[j].col;
                    b[current].col = a[j].row;
                    b[current].value = a[j].value;
                    current++;
                }
            }
        }
    }
}

위와 같이 알고리즘을 이용하여 희소행렬을 전치한다면 O(col * elements)의 시간복잡도 즉, 희소행렬의 col * 전체 원소의 수만큼 동작하게 된다. elements = row * col (전체 원소 수 = 행 크기 * 열 크기) 이므로 O (col^2 * row)의 시간복잡도를 가지게 된다. 일반 행렬을 전치시키면 O(row * col)만큼의 시간이 걸리므로 공간을 절약한 대신 시간 복잡도가 증가한 것을 확인할 수 있다.