2장 - 희소 행렬(Sparse Matrix)의 표현

행렬에 0이 많이 포함된 경우에 희소행렬이라고 한다.

배열에 희소행렬을 그대로 표현할 경우 공간낭비가 심하게 된다.

낭비되는 공간을 줄이기 위한 방법은 어떤게 있을까?

 

이차원 배열에 표현된 희소행렬을 

(행,열,값)으로 묶어 표현하는 방법이 있다

 

1	0	0
0	0	5
0	0	0

이런 배열일 있다고 하자.

이 때 (행,열,값)으로 묶어 표현하면

[(0,0,1),(1,2,5)] 로 적을 수 있겠다.

 

근데 이 방법이 항상 효율적인건 아니다.

n*n의 행렬이 있을 때, 0이 아닌 값이 k개 있다고 하자

2차원 배열로 행렬을 그대로 표현하면 n^2의 공간이 필요할 것이며

(행,열,값)으로 묶어 표현하면 3*k의 공간이 필요할 것이다.

이 방법이 효율적일 때는 k<(n^2)/3 이 된다. 

 

그건그렇고..

(행,열,값)으로 표현하면

연산은 어떻게 하지? ==> 다음시간에 계속..