Sparse Matrix (1) - 희소행렬이란?

Sparse Matrix, 희소행렬이란 행렬의 원소로 0이 많은 것을 의미한다.

 

즉 2차원 배열로 Matrix를 만들고, 원소들 중 0이 많이 있을 때 0을 위한 저장공간이 아깝기 때문에

 

이러한 메모리를 절약하기 위해 사용한다.

 

 

예를들어 다음과 같은 2차원 배열이 있다고 할 때

 

 

불필요하게 0을 저장하는 공간이 많아지기 때문에

 

다음과 같이 표현하는 것이다.

 

이는 구조체를 이용해서 배열을 만들어 주면 간단하게 1차원 배열로도 값을 표현해 낼 수 있다.

 

 

[0]번 인덱스에는 원래의 2차원 배열이 몇행 몇열로 이루어 져있고 값이 몇개인지가 저장되고,

 

[1]번 인덱스 부터 row값을 기준으로 0이 아닌 값들의 위치와 값이 저장된다.