방송대 자료구조 2강: 배열의 주소 계산과 희소행렬 표현
개발자는 A[3]처럼 인덱스로 원소를 찾지만, 컴퓨터는 시작 주소에서 몇 바이트 떨어졌는지를 계산한다. 이 두 관점을 연결하면 배열의 빠른 직접 접근, 행 우선·열 우선 저장 순서, 희소행렬에서 0을 생략하는 이유를 하나의 원리로 설명할 수 있다.
인덱스 하나가 값과 메모리 주소를 동시에 연결한다
배열은 일정한 차례에 따라 원소를 늘어놓은 자료구조다. 각 원소는 같은 자료형이므로 같은 크기의 메모리 공간을 차지하고, 인덱스와 원소값의 쌍으로 구분된다. 개발자가 보는 A[0], A[1], A[2]는 논리적인 위치이고, 실제 메모리에서는 각 원소가 연속된 물리 주소에 저장된다.
연속 저장은 직접 접근의 근거가 된다. 앞 원소부터 차례로 읽지 않아도 시작 주소, 인덱스, 원소 크기를 알면 원하는 위치를 곧바로 계산할 수 있다. 따라서 배열에서 인덱스를 안다는 것은 단순히 ‘몇 번째’인지 아는 것을 넘어, 해당 원소의 메모리 위치를 계산할 정보를 안다는 뜻이다.
판단 핵심: 배열의 순서는 값의 크기 순서가 아니라 메모리에 저장되는 원소의 물리적 순서다. 값이 90, 10, 50으로 배열되어 있어도 인덱스 0, 1, 2의 저장 순서는 그대로 유지된다.
추상자료형은 구현 코드보다 먼저 허용 연산을 정한다
추상자료형은 자료와 그 자료에 허용되는 연산을 논리적으로 정의한 설계 단계다. 반면 자료형 선언과 함수 코드는 특정 프로그래밍 언어로 그 설계를 구현한 결과다. 배열의 내부 메모리 표현을 몰라도 사용자가 생성·검색·저장 연산의 의미와 오류 조건을 이해할 수 있도록 경계를 세우는 것이 핵심이다.
| 연산 | 입력 | 정상 결과 | 확인할 조건 |
|---|---|---|---|
| create(n) | 배열 크기 n | 크기가 n인 빈 배열 생성 | 의도한 크기가 유효한가 |
| retrieve(a, i) | 배열 a, 인덱스 i | i 위치의 원소값 반환 | i가 인덱스 범위 안인가 |
| store(a, i, e) | 배열 a, 인덱스 i, 값 e | i 위치에 e를 저장 | i가 인덱스 범위 안인가 |
크기가 5이고 인덱스가 0부터 시작한다면 유효 범위는 0 <= i && i < 5다. 마지막 인덱스는 5가 아니라 4다. i <= 5로 검사하면 존재하지 않는 여섯 번째 위치를 허용하는 경계 오류가 생긴다.
구현을 읽는 법: 강의의 생성 코드는 다섯 원소를 0으로 초기화하는 흐름을, 검색과 저장 코드는 범위 검사 후 읽거나 쓰는 흐름을 보여 준다. 핵심은 문법 암기가 아니라 ‘검사 → 정상 연산 또는 오류 처리’라는 분기다.
검색과 저장은 같은 경계 검사를 거쳐 서로 다른 일을 한다
검색 연산은 배열을 바꾸지 않고 지정 위치의 값을 반환한다. 저장 연산은 지정 위치의 값을 새 값으로 바꾼다. 예를 들어 배열이 [10, 20, 30, 40, 50]일 때 retrieve(a, 2)는 30을 돌려주며 배열은 그대로다. store(a, 3, 35)를 수행하면 네 번째 원소만 40에서 35로 바뀐다.
두 연산 모두 먼저 인덱스가 0 이상이고 배열 크기보다 작은지 확인한다. 이 검사를 생략하면 논리적으로 배열에 속하지 않는 메모리를 읽거나 쓸 수 있다. 특히 저장의 범위 오류는 다른 데이터까지 손상시킬 수 있으므로 ‘쓰기 전에 검사’가 연산 순서에서 빠져서는 안 된다.
직접 구성한 실행 추적
- 초기 배열을 [8, 6, 4, 2]라고 가정한다.
retrieve(a, 1)은 범위0 <= 1 < 4를 만족하므로 6을 반환한다.store(a, 2, 9)는 범위를 만족하므로 배열을 [8, 6, 9, 2]로 바꾼다.retrieve(a, 4)는4 < 4가 거짓이므로 값을 읽지 않고 오류로 처리해야 한다.
1차원 주소식은 시작점에 원소 크기만큼의 이동을 더한다
배열 A의 첫 원소 A[0]의 시작 주소를 α, 원소 하나의 크기를 k바이트라고 하자. 인덱스가 0부터 시작하면 A[i] 앞에는 원소 i개가 있으므로 주소는 α + i×k다. 인덱스의 하한이 L인 일반적인 표현에서는 주소(A[i]) = α + (i-L)×k로 쓸 수 있다.
주소를 단계별로 계산하기
학습을 위해 시작 주소가 1,200이고 정수 원소 하나가 4바이트인 배열을 가정하자. A[3]의 주소는 다음 순서로 구한다.
- A[3] 앞에는 A[0], A[1], A[2] 세 원소가 있다.
- 건너뛸 바이트 수는
3×4=12다. - 시작 주소에 더하면
1,200+12=1,212다.
주소를 1,203으로 쓰는 풀이는 인덱스를 바이트 수로 착각한 것이다. 인덱스 차이에 반드시 원소 크기 k를 곱해야 한다. 반대로 원소 크기가 1바이트일 때만 인덱스 증가량과 주소 증가량이 우연히 같다.
2차원 배열도 메모리에서는 한 줄로 펴서 저장한다
행렬은 행과 열을 가진 2차원 구조이지만 메모리는 일렬로 이어진 주소 공간이다. 따라서 어느 방향을 먼저 이어 붙일지 정해야 한다. 행 우선 저장은 한 행의 열 원소를 연속으로 놓은 뒤 다음 행으로 이동하고, 열 우선 저장은 한 열의 행 원소를 연속으로 놓은 뒤 다음 열로 이동한다.
| 저장 방식 | 2×3 배열의 위치 순서 | 한 행 r, 열 c에서 앞선 원소 수 |
|---|---|---|
| 행 우선 | [0,0] → [0,1] → [0,2] → [1,0] → [1,1] → [1,2] | r×열 수 + c |
| 열 우선 | [0,0] → [1,0] → [0,1] → [1,1] → [0,2] → [1,2] | c×행 수 + r |
예를 들어 3행 5열 배열 A[3][5]의 A[2][3]을 생각하자. 행 우선이면 앞선 원소 수는 2×5+3=13개다. 열 우선이면 3×3+2=11개다. 같은 논리 좌표라도 저장 규칙이 달라지면 물리적 오프셋이 달라진다.
오개념 교정: 행 우선과 열 우선은 배열을 화면에 어떻게 그리는지가 아니라 메모리에 어느 원소를 먼저 연속 배치하는지의 차이다. 행과 열의 이름만 바꾸지 말고, 목표 위치보다 앞에 저장되는 원소를 실제로 세어 검산한다.
행 우선 주소는 완성된 행과 현재 행의 열을 합쳐 구한다
0부터 시작하는 R×C 배열에서 행 우선 오프셋은 r×C+c다. 목표 행 r보다 앞에 완성된 행이 r개 있고, 각 행에 C개 원소가 있으므로 r×C개를 먼저 건너뛴다. 그다음 현재 행에서 c개를 더 건너뛴다. 실제 바이트 주소는 이 오프셋에 원소 크기 k를 곱하고 시작 주소 α를 더한 α+(r×C+c)×k다.
직접 구성한 예로 시작 주소 500, 원소 크기 2바이트인 4×6 배열에서 A[2][4]를 찾으면 오프셋은 2×6+4=16이다. 바이트 이동량은 16×2=32, 최종 주소는 500+32=532다. 오프셋 16과 주소 532를 구분해야 한다.
검산 질문: ‘앞에 완성된 행이 몇 개인가 → 행마다 원소가 몇 개인가 → 현재 행에서 몇 칸 더 가는가 → 원소가 몇 바이트인가’의 순서로 묻는다.
희소행렬은 0의 위치보다 0이 아닌 항목만 기록한다
희소행렬은 원소값이 0인 원소가 0이 아닌 원소보다 상대적으로 많은 행렬이다. 일반적인 2차원 배열로 저장하면 값 0에도 다른 원소와 같은 공간이 배정된다. 0이 대부분인 경우에는 이 공간이 실제 정보보다 훨씬 커질 수 있다.
강의의 효율적 표현은 0인 원소를 저장하지 않고, 0이 아닌 원소마다 행·열·값의 세 정보를 기록한다. 표의 첫 행에는 전체 행 수, 전체 열 수, 0이 아닌 원소 수를 기록한다. 강의 예에서는 첫 행의 8, 9, 10이 각각 8행, 9열, 비영 원소 10개를 뜻한다. 뒤의 행들은 (0,1,20), (0,4,9), (0,7,11)처럼 실제 항목의 위치와 값을 나타낸다.
| 저장 방식 | 필요한 값의 수 | 유리한 상황 | 주의점 |
|---|---|---|---|
| 일반 2차원 배열 | 행 수×열 수 | 0이 적고 대부분의 칸에 값이 있음 | 희소할수록 0 저장이 많아짐 |
| 행·열·값 목록 | 머리 정보 3개 + 비영 원소당 3개 | 0이 매우 많고 비영 원소가 적음 | 위치를 함께 저장하는 비용이 있음 |
저장량을 직접 비교하기
학습을 위해 20×20 행렬에 0이 아닌 원소가 12개뿐이라고 가정하자. 일반 배열은 400개의 값을 저장한다. 행·열·값 목록은 머리 정보 3개와 항목 정보 12×3=36개를 합쳐 39개의 값을 저장한다. 이 경우 39가 400보다 작으므로 압축 표현이 유리하다. 그러나 비영 원소가 150개라면 3+150×3=453이 되어 단순 저장량만으로는 일반 배열보다 불리하다.
새 배열 문제는 위치·순서·밀도를 차례로 판정한다
- 위치: 인덱스의 시작값과 유효 범위를 확인한다. 크기 n이면 0 기반 마지막 인덱스는 n-1이다.
- 주소: 논리 인덱스를 원소 개수의 오프셋으로 바꾸고, 원소 크기를 곱한 뒤 시작 주소를 더한다.
- 순서: 2차원 배열이면 행 우선인지 열 우선인지 먼저 정하고 앞선 원소 수를 센다.
- 밀도: 0이 대부분이면 전체 칸 저장과 행·열·값 목록의 저장량을 비교한다.
자가 점검으로 “배열 크기 6에서 인덱스 6은 유효한가?”, “원소 크기 8바이트라면 인덱스가 1 증가할 때 주소는 얼마 증가하는가?”, “3×4 행 우선 배열의 [2,1] 앞에는 몇 원소가 있는가?”를 답해 보자. 정답은 각각 유효하지 않음, 8바이트, 2×4+1=9개다.
핵심 개념 정리
- 배열의 인덱스는 논리적 위치이며, 같은 크기의 원소가 연속 저장되므로 실제 주소를 계산할 수 있다.
- 생성·검색·저장 연산은 추상자료형의 인터페이스이며, 검색과 저장 전에는 유효 인덱스 검사가 필요하다.
- 1차원 주소는 시작 주소에 ‘앞선 원소 수×원소 크기’를 더해 구한다.
- 2차원 배열은 행 우선 또는 열 우선으로 선형화되며, 저장 순서에 따라 같은 좌표의 오프셋이 달라진다.
- 희소행렬은 비영 원소의 행·열·값만 기록해 0 저장을 줄이지만, 비영 원소가 많아지면 목록의 위치 정보 비용도 비교해야 한다.
전체 사고 흐름: 배열 문제를 만나면 먼저 인덱스 범위를 정하고, 논리 위치를 선형 오프셋으로 바꾸며, 원소 크기로 물리 주소를 계산한다. 다차원이면 저장 순서를, 값이 드문 행렬이면 표현별 저장량을 추가로 확인한다.
예상문제 10선
1. 배열의 직접 접근이 가능한 가장 핵심적인 이유는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 값의 정렬 여부는 주소 계산과 무관하며 배열은 정렬되지 않은 값도 저장한다.
- ② 오답: 배열은 여러 원소를 저장하는 구조이므로 정의 자체와 어긋난다.
- ③ 정답: 시작 주소와 원소 크기, 인덱스로 목표 원소의 오프셋을 바로 구할 수 있다.
- ④ 오답: 인덱스는 위치를 나타내며 원소값을 별도로 복사해 두는 저장소가 아니다.
2. retrieve와 store 연산의 차이를 옳게 설명한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 검색은 읽기, 저장은 쓰기이며 두 연산 모두 유효한 인덱스를 전제로 한다.
- ② 오답: 잘못된 위치의 쓰기도 위험하므로 store 역시 같은 범위 검사가 필요하다.
- ③ 오답: 검색과 저장은 기존 배열의 크기를 변경하거나 배열 자체를 삭제하지 않는다.
- ④ 오답: 새 배열을 만드는 역할은 create 연산에 해당한다.
3. 크기 5인 0 기반 배열의 범위 검사로 잘못된 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 인덱스 0부터 4까지만 허용하는 올바른 범위 조건이다.
- ② 오답: 0 기반 배열에서 0은 첫 원소의 유효한 인덱스다.
- ③ 오답: 크기 5인 배열의 마지막 인덱스는 4이므로 올바른 판정이다.
- ④ 정답: 존재하지 않는 인덱스 5까지 허용하여 배열 경계를 한 칸 벗어나게 한다.
4. 시작 주소가 1,200이고 원소 크기가 4바이트인 0 기반 배열에서 A[3]의 주소는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 인덱스 3을 바이트 이동량으로 사용해 원소 크기 4를 곱하지 않았다.
- ② 정답: 앞선 세 원소가 차지하는 12바이트를 시작 주소에 더해
1,200+3×4=1,212다. - ③ 오답: 목표 원소까지 네 원소를 건너뛴 것으로 세어 한 칸 더 이동했다.
- ④ 오답: 시작 주소에 원소 크기를 곱했으며 주소식의 덧셈 관계를 잘못 적용했다.
5. 행 우선으로 2×3 배열을 메모리에 놓을 때 올바른 순서는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 같은 열의 행을 먼저 바꾸는 열 우선 순서다.
- ② 오답: 행과 열 어느 방향도 일정하게 진행하지 않아 연속 저장 규칙과 맞지 않는다.
- ③ 정답: 0행의 세 열을 모두 저장한 뒤 1행의 세 열을 저장한다.
- ④ 오답: 행 우선의 역순이며 인덱스가 증가하는 기본 저장 흐름과 다르다.
6. 3행 5열 배열의 A[2][3] 앞에 저장된 원소 수를 행 우선 방식으로 계산하면?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 행과 열 인덱스를 단순히 더해 열 수를 반영하지 않았다.
- ② 오답:
3×3+2로 계산한 열 우선 오프셋이다. - ③ 오답: 두 완성 행의 10개에 현재 행의 인덱스 3이 아니라 한 행 전체 5개를 더했다.
- ④ 정답: 앞선 두 행의 10개와 현재 행의 세 원소를 합쳐
2×5+3=13개다.
7. 같은 2차원 배열의 행 우선 저장과 열 우선 저장을 구분하는 기준은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 두 방식은 다차원 원소를 일렬 메모리에 펴는 우선 방향이 다르다.
- ② 오답: 원소값의 부호는 물리적 저장 순서를 결정하지 않는다.
- ③ 오답: 검색과 저장은 연산 종류이며 다차원 선형화 방식과 다른 구분축이다.
- ④ 오답: 인덱스 하한은 주소식 보정에 필요하지만 행·열 우선의 결정 기준은 아니다.
8. 20×20 행렬에 비영 원소가 12개일 때 행·열·값 목록에 저장할 값의 수는? 단, 첫 행에 행 수·열 수·비영 원소 수를 기록한다.
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 비영 원소의 개수만 세고 각 원소의 행·열·값 정보를 빠뜨렸다.
- ② 정답: 머리 정보 3개와 비영 원소 정보
12×3=36개를 합쳐 39개다. - ③ 오답: 비영 원소 12개의 세 항목만 세고 첫 행의 머리 정보 3개를 누락했다.
- ④ 오답: 모든 칸을 저장하는 일반 2차원 배열의 값 수다.
9. 희소행렬을 가장 정확히 설명한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 정사각행렬 여부와 희소성은 서로 다른 성질이다.
- ② 오답: 일부 비영 원소가 있어도 0이 상대적으로 많으면 희소행렬이다.
- ③ 오답: 희소성은 값의 분포에 관한 개념이며 모든 비연속 저장 배열을 뜻하지 않는다.
- ④ 정답: 전체 원소 중 0이 차지하는 비중이 높아 압축 표현을 고려할 수 있는 행렬이다.
10. 배열 문제를 해결하는 순서로 가장 적절한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 논리적 유효성, 선형 위치, 물리 주소, 저장 효율을 차례로 점검하는 재사용 가능한 절차다.
- ② 오답: 값 정렬은 필수 조건이 아니며 범위 검사를 생략하면 안전한 접근을 보장할 수 없다.
- ③ 오답: 원소 크기와 다차원 저장 순서를 빼면 주소가 달라지고, 희소성의 이점도 잃는다.
- ④ 오답: 원소 크기는 바이트 이동량을 계산하는 값이며 범위 검사는 읽기·쓰기 전에 수행해야 한다.
참고 자료와 작성 기준
이 글은 방송대 컴퓨터과학과 「자료구조」 2강 ‘배열’ 강의록을 바탕으로 개념 관계와 계산 과정을 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 주소 계산과 저장량 비교의 추가 수치는 강의의 원리를 연습하도록 직접 구성한 가정입니다.
- 작성·편집: 올에이클래스 학습연구팀
- 주요 근거: 방송대 컴퓨터과학과 「자료구조」 2강 ‘배열’ 강의록(2023년 제작 자료)
- 외부 보충 자료: 사용하지 않음
- 편집 원칙: 올에이클래스 편집 정책
- 최종 내용 검토: 2026-08-18
댓글
댓글 쓰기