[C언어] 희소 행렬의 구현 (Spars Matrix)

희소 행렬이란, 

행렬의 대부분이 0을 가리키는 행렬이다. 

희소 행렬의 경우 배열의 크기가 커질 수록 0이 차지하는 메모리가 많아지기 때문에 메모리의 낭비가 매우 심하다. 

따라서 희소 행렬에서 0이 아닌 원소들만 따로 배열로 만들어서 정리할 수 있다. 

 

 

좌측의 이미지가 바로 희소 행렬이다.

6X6 크기의 행렬에 대부분이 0으로 이루어져 있어 메모리의 낭비가 심하다. 

따라서 우측과 같은 형태로 배열을 정리해주는 것이다.

쉽게 말하자면 핵심을 압축한 새로운 행렬을 만드는 것이라 할 수 있다. 

 

우측 행렬의 행 부분은 좌측 행렬의 0이 아닌 원소의 개수와 같다. 

우측 행렬의 열 부분은 차례로 0이 아닌 원소들의 행 인덱스 / 열 인덱스 / value 값이다.

즉 원래 행렬에서 0이 아닌 값들의 위치와 값을 [number][3] 크기의 새로운 행렬로 생성한 것이다. 

 

희소 행렬의 구현 방법 

희소 행렬의 구현 알고리즘은 다음과 같다.

(*  원래 배열을 original[][], 희소행렬을 Spars[][]라고 하자.)

 

1) original 배열을 for문으로 돌며 0이 아닌 원소의 개수를 찾아 size 변수에 저장한다.

2) Spars[Size][3] 의 크기인 새로운 2차원 배열을 생성한다. 

3) for문을 돌며,

Spars[Size][0] 엔 원소의 행 인덱스 값을,

Spars[Size][1] 엔 원소의 열 인덱스 값을,

Spars[Size][2] 엔  원소의 Value를 저장한다. 

 

희소 행렬의 Code

매개변수로는 original 2차원 배열과 배열의 행열 크기를 받아온다. 

size 변수를 초기화하고, for문을 돌며 0이 아닌 원소의 개수를 구한다.

 

새로운 Spars 배열을 생성하였다. 

참고로 말하지만, array() / freeArray() / printArray()는 기본 함수가 아닌 내가 구현한 배열 관련 함수이다. 

이후 for문을 돌며 각 위치에 원소의 행, 열, 값을 저장한다. 

 

main 함수이다. 

original 배열을 동적할당 받은 후 난수값을 저장한다. 

하나 아쉬운 게 있다면 난 여기서 0이 많은 배열을 구현하지 못했다ㅜㅜ,,, 어케 하는지 모르겠음 ㅠ

일반 배열을 구성하고 배열을 출력한 후 free 해주었다. 

 

아쉽,,, 담에 시간 많을 때 다시 구현해 봐야겠당