[자료구조] 행렬의 순차 자료구조 표현

행렬 (matrix)

 - m x n 행렬

    ㄴ m : 행의 개수

    ㄴ n : 열의 개수

    ㄴ 원소의 개수 : (m xn) 개

행렬 A =	a11	a12	...	a1n
	a21	a22	...	a2n
	. .	. .	. .	. .
	am1	am2	...	amn

전치 행렬

 - 행렬의 행과 열을 서로 교환하여 구성한 행렬

 - 행렬 A의 모든 원소의 위치(i, j)를 (j, i)로 교환

 - mxn 행렬을 nxm 행렬로 변환한 행렬 A'는 행렬 A의 전치 행렬

 ex)

A =	1	2	3	4
	5	6	7	8
	9	10	11	12

전치 행렬 변환↓

A' =	1	5	9
	2	6	10
	3	7	11
	4	8	12

행렬의 순차 자료구조 표현

 - 2차원 배열 사용 : mxn행렬을 m행 n열의 2차원 배열로 표현

 ex)

A =	1	2	3	4
	5	6	7	8
	9	10	11	12

 A [3][4]

	[0]	[1]	[2]	[3]
[0]	1	2	3	4
[1]	5	6	7	8
[2]	9	10	11	12

 

 - 희소 행렬에 대한 2차원 배열 표현

    ㄴ 희소 행렬 A는 배열의 원소 12개 중 실제 사용하는(원소를 저장하는)것은 3개뿐이므로 9개의 메모리 공간 낭비

    ㄴ 희소 행렬인 경우에는 0이 아닌 원소만 추출하여 <행 번호, 열 번호, 원소> 쌍으로 배열에 저장

	[0]	[1]	[2]	[3]	->	순서쌍
[0]	0	2	0	4		<0, 1, 2>
[1]	0	0	0	0		<0, 3, 4>
[2]	9	0	0	0		<2, 0, 9>

    ㄴ 추출한 순서쌍을 2차원 배열의 행으로 저장

    ㄴ 원래의 행렬에 대한 정보를 순서쌍으로 작성하여 0번 행에 저장 <전체 행의 개수, 전체 열의 개수, 0이 아닌 원소의 개수>

순서쌍	->		[0]	[1]	[2]
		[0]	3	4	3
<0, 1, 2>		[1]	0	1	2
<0, 3, 4>		[2]	0	3	4
<2, 0, 9>		[3]	2	0	9