[자료구조] 3. 배열

1. 배열

1) 변수

• 프로그램에서 자료를 저장할 수 있는 기억 장소

• 변수의 값은 계속 변할 수 있으며 하나의 값만 저장 가능

• 한꺼번에 많은 자료를 처리해야 하는 경우 배열(array) 사용

 

2) 배열(array)

• 같은 자료형을 가진 자료들을 나열하여 메모리에 연속으로 저장한 자료들의 그룹

• 인덱스(index) : 배열의 요소를 간단히 구별하기 위해 사용하는 번호 (C에서 인덱스는 0부터 시작)

• 모든 자료형에 대해 배열로 구성 가능

• 구성 형태에 따라 1차원 배열, 2차원 배열, 3차원 배열 등으로 구분

 

3) 1차원 배열

• 가장 단순한 배열 형태

• 인덱스를 통해 원소의 위치를 표시하며, 원소 자체의 이름은 없음

 

선언 방법

• 자료형: 배열 원소들의 자료형 (모든 원소는 같은 자료형)

• 배열이름: 배열의 원소에 접근할 수 있는 유일한 이름

• 배열의 개수: 배열 원소의 개수를 나타내는 정수 (인덱스는 0부터 배열 크기-1까지)

- 자료형 배열이름[배열의 개수];

 

4) 2차원 배열

• 2개의 1차원 배열로 구성되며 첨자는 2개 사용

• 가로 줄은 행(row), 세로 줄은 열(column)

 

선언 방법

• 배열이름: 2차원 배열의 이름

• 행의 개수: 가로 줄 개수

• 열의 개수: 세로 줄 개수

- 자료형 배열이름[행의 개수][열의 개수];

 

5) 3차원 배열

• 여러 개의 2차원 배열로 구성됨

• 면, 행, 열 3개의 첨자를 이용하여 원소를 구별

 

선언 방법

• 면의 개수: 3차원 배열의 면 개수

• 행의 개수: 가로 줄 개수

• 열의 개수: 세로 줄 개수

- 자료형 배열이름[면의 개수][행의 개수][열의 개수];

 

2. 배열의 표현

1) 배열

• 동일 크기의 항목들이 순서를 갖고 배열된 자료구조

• 첨자의 수에 따라 1차원 배열, 2차원 배열 등으로 구분

 

주기억장치에서 번지의 표시

• 절대 번지(absolute address) 사용

• 매핑(mapping) : 인덱스(index)와 값(value) 매칭

 

2) 1차원 배열

• 기억 장소에 순서대로 저장됨

• 1차원 배열의 물리적 저장은 논리적 순서와 동일함

 

벡터(Vector)

• 행 벡터: 세로로 나열된 벡터 (n×1)

• 열 벡터: 가로로 나열된 벡터 (1×n)

 

3) 다차원 배열

• 2개 이상의 첨자를 사용하여 원소를 구별

 

다차원 배열 저장 기법

• 행우선 방식(row major): 행 순서대로 저장됨

• 열우선 방식(column major): 열 순서대로 저장됨

 

2차원 배열 A[3][3]의 저장 순서 예시

• 행우선 방식: A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], A[1][2], A[2][0], A[2][1], A[2][2]

• 열우선 방식: A[0][0], A[1][0], A[2][0], A[0][1], A[1][1], A[2][1], A[0][2], A[1][2], A[2][2]

 

메모리 주소 계산

• 행우선 주소: 기본주소 + (i × n + j) × k

• 열우선 주소: 기본주소 + (j × m + i) × k

 

3. 희소 행렬

1) 행렬(matrix)

• 여러 개의 숫자를 직사각형 형태로 배열한 것

• 행(row)과 열(column)로 구성됨

• m×n 행렬: m개의 행과 n개의 열로 구성되며 원소 개수는 m × n

 

2) 희소 행렬(sparse matrix)

• 대부분의 원소가 0으로 구성된 행렬

• 0을 저장하는 것은 메모리 낭비가 발생하므로 비효율적

 

3) 해결책

0이 아닌 원소만 저장

• <행, 열, 값> 쌍으로 배열에 저장

• 첫 번째 행에 <전체 행 수, 전체 열 수, 0이 아닌 원소 수>를 저장하여 정보 유지

 

4) 희소 행렬의 2차원 배열 표현

• 예시: 8×7 행렬 → 56개 공간 필요

• 0이 아닌 원소만 표현하면 11×3=33개만 사용

• 원래 행렬 정보는 <8, 7, 10> 형태로 첫 번째 행에 저장

 

5) 배열을 이용한 희소 행렬 표현

• m × n 행렬의 메모리 사용량이 크므로 0이 아닌 원소만 저장하는 방식 적용

• 문제점: 연산 시 반복적인 패턴을 찾기 어려워 비효율적

 

6) 해결책: 연결 리스트 표현

• 0이 아닌 값만 연결 리스트로 저장하여 메모리 효율 향상

• 삽입과 삭제 연산이 자유로움

• 필요한 부분만 리스트로 만들어 자료구조가 간단하며 메모리 낭비 절약

---

이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.