[자료구조] 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이 아닌 값만 연결 리스트로 저장하여 메모리 효율 향상
• 삽입과 삭제 연산이 자유로움
• 필요한 부분만 리스트로 만들어 자료구조가 간단하며 메모리 낭비 절약
이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.