자료구조(7) - 희소행렬

 - 희소행렬

               : 희소행렬이란 배열에서 대부분의 원소가 0인 행렬이다.

               : 0은 빈 값이기 떄문에, 요소의 위치가 연속적이지 않은 행렬이다.

               : 배열의 lenght값보다 원소의 갯수가 현저히 적은 행렬이다.

               : 재밌는 표현방법이 많아 가져와보았다.

               : 반대되는 표현으로는 조밀행렬 밀집행렬이 있다.

 

그림을 그리기 어려워

 

Random r = new Random();
		
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				System.out.print(r.nextInt(2)+" ");
			}
			System.out.println("");
		}

 

이렇게 그려보겠다.

 

0 1 0 0 1 0 1 1 0 0 
1 0 0 1 0 0 0 1 1 0 
0 0 1 0 0 0 1 0 1 1 
0 0 0 1 1 0 0 1 0 0 
0 1 1 0 1 1 1 0 1 0 
1 1 0 0 1 1 1 0 1 0 
0 1 1 1 1 1 1 0 0 1 
0 1 0 0 1 1 0 0 1 1 
0 0 1 0 1 1 1 1 0 1 
0 0 1 1 0 0 1 1 0 1 

 

이러한 절반정도의 0이 나왔다. 책의 예시에는 많은 0 이 있었지만 느낌적으로 전달되면 좋겠다.

실제로 대부분의 원소가 0이라는게 명확한 기준이 없지않은가

 

               : 개념적으로 희소성은 시스템들이 약하게 연결된 것에 해당한다.

                 한 줄로 나열된 공과 공이 스프링으로 양 옆으로 하나씩 연결되었을 때 이것은 희소 시스템이다.

                 그와 반대로 한 줄의 공들이 여러 방향의 공들과 스프링으로 연결되었을 때

                 이 시스템은 밀집 행렬이 될 수 있다.

                  희소의 개념은 조합론과 네트워크 이론 등과 같은 응용분야에서 유용하다.

                  <출처 : ko.wikipedia.org/wiki/%ED%9D%AC%EC%86%8C%ED%96%89%EB%A0%AC >

                  < 이 내용은 네트워크 이론을 익히게된 이후에 다시 다뤄보겠다. >

 

 

               : 이 경우 모든 0의 값을 정의하게되어 행렬그대로 표현하면 메모리의 효율이 좋지않다.

                           : 0이 아닌 값들만을 모아 2차원 배열로 만들경우 메모리의 효율을 올릴 수 있으나,

                             다른 연산이 복잡해지는 단점이 있다.

                            ex) arr( 행, 열, 값)