[Data Structure] CHAP 4. Sparse Matrices(희소행렬) - C언어 ver.

학교 강의 2번째 강의자료 마지막 학습 키워드 Sparse Matrix이다. 그냥 matrix는 1학년 2학기 전산통계학시간에 배워서 알고 있었으나 sparse matrix는 생소했다. 이번 챕터에서는
✅ Sparse Matrix란?
✅ Sparse Matrix의 ADT와 표기법
이 두가지를 학습할 예정이다.

---

1. Sparse Matrix

Sparse는 사전적으로 '드문, 희박한'의 뜻을 가지고있다. 즉, 가치있는 값을 가지고 있는 항이 적은 매트릭스를 의미한다.

• matrix : 값이 숫자인 배열이 행과 열 형태로 이루어져있는 데이터구조의 종류이다.
• sparse matrix : matrix중에서 값이 0인 요소들이 많은 매트릭스를 의미한다.

값이 0인 요소가 많으면 메모리 낭비가 심해질 수밖에 없다. 6x6 매트릭스에서 30개가 0이라면 메모리 낭비가 적어보일 수 있지만 1000x1000 매트릭스인 상황에서 2000개만 0이 아닌 값을 가진다면, 이는 99만8000개의 메모리를 낭비하는 꼴이 된다.

이를 방지하기 위한 sparse matrix 표기법이 있다. 관련 내용은 아래에 이어서 설명할 것이다.

---

2. Sparse Matrix의 ADT와 표기법

ADT SparseMatrix is
	objects : A set of triples, <row, column, value>, where row and column are integers and 
    form a unique combination, and value comes from the set item
    
    funtions : 
    	for all a,b ∈ SparseMatrix, x∈item, i, j, maxCol, maxRow∈index
        SparseMatrix Create(maxRow, maxCol) ::=
        									return a SparseMatrix that can hold up to
                                            maxItems = maxRow x maxCol and whose
                                            maximum row size is maxRow and whose
                                            maximum column size is maxCol.
        SparseMatrix Transpose(a) ::=
        									return the matrix produced by interchanging the row
                                            and column value of every triple
        SparseMatrix Add(a,b) ::=			
        									if the dimensions of a and b are the same
                                            return the matrix produced by adding corresponding
                                            items, namely those with identical row and column values.
                                            else return error
        SparseMatrix Multiply(a,b) ::=
        									if number of columns in a equals number of rows in b
                                            return the matrix d produced by multiplying a by b according to the
                                            formula: d[i][j] = ∑(a[i][k] * b[k][j]) where d(i,j) is the (i,j)th element
                                            else return error.

다음과 같이 수도코드를 이용한 ADT를 작성할 수 있으며, 0이 아닌 값을 갖는 요소를 (row, column, value) 이렇게 트리플 형식으로 작성하겠다는 것이다.

Sparse Matrix 작성법

대략 a의 형태로 작성이 가능하다. 값이 0이 아닌 요소의 행과 열 위치와 값을 작성한다. 행과 열 값의 순서를 바꾼것이 b이다.