배열의 표현과 응용

최종 수정 : 24.12.27

배열의 표현과 응용

1. 다차원 배열의 행우선과 열우선

배열은 행의 순서대로 연속 저장되는 방법은 행우선 방식과 열의 순서대로 연속저장되는 열우선 방식이 있다.

 

1) 1차원 배열

논리적 표현은 왼쪽에서 오른쪽으로으로 순서대로 나열되며, 물리적으로 기억공간에서 연속적인 공간에 저장된다.

배열원소의 위치 = 배열의 시작주소(배열명) + 인덱스 * 한 개의 원소(데이터 타입)크기

 

2) 2차원 배열

2차월 배열은 행 우선과 열 우선으로 표현할 수 있다. 배열 a[m][n]에 대해 원소 a[i][j]의 위치는 다음과 같다.

 

행우선 방식

• 위치 : (i * n) + j + 1
• 저장된 주소 : a + ((i * n) + j) * l

열우선 방식

• 위치 : (j * m) + i + 1
• 저장된 주소 : a + ((j * m) + i) * l

3) 3차원 배열

2차원의 행우선과 열우선 방식과 동일하게 적용되며 이전 면에 대한 위치만 표현하면 된다.

 

ex) 3차원 배열 [3][4][5]에서 [2][1][2]의 위치를 구하시오. 단, 배열의 인덱스가 0으로 시작하는 것을 기준으로 한다.

행 우선 방식

• 위치 : k * (m * n) + (i * n) + j + 1 = 2 * (4 * 5) + (1 * 4) + 2 + 1 = 47번째

 

열 우선 방식

• 위치 : k * (m * n) + (j * m) + i + 1 = 2 * (4 * 5) + (2 * 3) + 1 + 1 = 48번째

---

2. 희소 행렬의 표현

행렬은 실제적인 문제에서 발생하는 것을 수학적으로 표현하여, 연산을 효율적으로 실행하기 위해 사용된다. 행렬은 2차원배열과 같은 구조이다. 단, 희소 행렬은 대부분 0이고 일부의 원소만 값을 가지는데 기억할 필요 없는 0을 저장하기 위해 기억공간을 낭비하게 되는데 이를 다르게 리스트로 저장할 수 있다.

대각선의 원소들이 0인 것이 특징이다.

 

아래 그림의 회소행렬을 리스트로 표현하시오

	[1]	[2]	[3]	[4]	[5]
[1]	0	23	0	0	0
[2]	-9	0	0	0	0
[3]	0	0	0	0	0
[4]	0	0	45	0	0
[5]	1	0	0	5	0

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

5 (전체 행수)	5 (전체 열수)	5 (0이 아닌 원소 수)
0 (첫 데이터의 행수)	1 (첫 데이터의 열수)	23 (첫 데이터)
1	0	-9
3	2	45
4	0	1
4	3	5

 

희소행렬을 연결 리스트로 표현하는 것은 기억공간의 낭비를 해결하고 행렬을 효율적으로 사용할 수 있다.

---

3. 전치행렬

행렬에서 행과 열이 바뀌는 행렬이다.

---

참고

독학사 교재