왜 배열의 메모리 배치부터 정확히 알아야 하는가

03편(배열과 메모리 배치의 기초)에서 배열이 데이터를 “연속된 메모리 공간”에 순서대로 쌓아 두는 자료구조라는 감각을 잡았다. 이 편에서는 그 감각을 시험에서 바로 계산에 쓸 수 있는 수준까지 끌어올린다. 독학사 시험은 “2차원 배열 A[3][4]에서 A[2][1]의 주소를 구하라” 같은 주소 계산 문제와 “배열의 중간에 원소를 삽입할 때 몇 번의 이동이 일어나는가” 같은 연산 횟수 계산 문제를 자주 낸다. 두 문제 모두 배열이 “인덱스로 위치를 계산해 바로 접근하는 구조”라는 원리를 정확히 알아야 풀린다.

쉽게 말하면: 배열은 데이터를 나란히 줄 세워 놓고, 몇 번째 칸인지만 알면 계산만으로 그 칸의 주소를 바로 찾아낼 수 있는 자료구조다.

1차원 배열의 주소 계산

배열은 메모리에서 시작 주소(base address)로부터 원소 하나의 크기만큼씩 떨어진 자리에 원소들을 나란히 저장한다. 인덱스가 i인 원소의 주소는 다음과 같이 계산한다.

• $\text{base}$: 배열의 시작 주소(배열의 첫 원소 A[0]이 있는 주소)
• $i$: 접근하려는 원소의 인덱스
• $\text{size}$: 원소 하나가 차지하는 바이트 크기(예: int는 보통 4바이트)

예를 들어 int A[5]가 주소 1000번지부터 시작한다고 하면(int는 4바이트 가정), A[3]의 주소는 다음과 같다.

이 계산이 상수 시간, 즉 $O(1)$인 이유는 인덱스가 몇이든 곱셈과 덧셈 한 번이면 끝나기 때문이다. 배열의 가장 큰 장점인 “인덱스로 즉시 접근(임의 접근, random access)“이 바로 이 계산 한 번으로 이루어진다는 사실을 기억해 두자.

자주 틀리는 점: 배열의 인덱스가 1부터 시작한다고 착각하는 경우가 있다. C를 비롯한 대부분의 언어에서 배열 인덱스는 0부터 시작하므로, A[3]은 “네 번째 원소”이지 “세 번째 원소”가 아니다.

다차원 배열의 주소 계산

2차원 배열은 저장 방식에 따라 행 우선(row-major)과 열 우선(column-major) 두 가지로 나뉜다. C 언어는 행 우선 방식을 쓴다. 행 우선이란 같은 행의 원소들을 먼저 다 저장한 다음 다음 행으로 넘어가는 방식이다.

int A[3][4](3행 4열)가 주소 1000번지부터 시작하고 int가 4바이트라면, A[i][j]의 주소는 다음과 같다.

• $i$: 행 인덱스, $j$: 열 인덱스
• 열의 개수: 한 행에 들어 있는 원소 수(여기서는 4)

A[2][1]의 주소를 계산해 보자.

이 계산에서 $2 \times 4$는 “0행·1행을 완전히 건너뛴 만큼의 원소 개수”이고, 여기에 $+1$을 더한 것은 “2행 안에서 1번째 칸까지 더 간다”는 뜻이다. 행 우선 배치를 표로 확인하면 다음과 같다.

표에서 A[2][1]이 저장 순서 9번째, 주소 1036번지에 있음을 바로 확인할 수 있다. 열 우선 방식(포트란(Fortran) 등에서 사용)은 반대로 같은 열을 먼저 다 저장하며, 주소 공식은 $\text{base} + (j \times \text{행의 개수} + i) \times \text{size}$로 행과 열의 역할이 바뀐다.

쉽게 말하면: 행 우선은 “가로줄을 다 채우고 다음 줄로”, 열 우선은 “세로줄을 다 채우고 다음 줄로” 넘어가는 저장 순서 차이이며, C는 행 우선을 쓴다.

배열의 탐색

배열에서 특정 값을 찾는 가장 기본적인 방법은 순차 탐색(sequential search)이다. 정렬 여부와 관계없이 앞에서부터 하나씩 비교한다.

#include <stdio.h>
 
int sequentialSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;  // 찾은 인덱스 반환
        }
    }
    return -1;  // 못 찾으면 -1
}
 
int main(void) {
    int arr[] = {40, 10, 90, 25, 60};
    int n = 5;
    int result = sequentialSearch(arr, n, 25);
    printf("25의 위치: %d\n", result);
    result = sequentialSearch(arr, n, 100);
    printf("100의 위치: %d\n", result);
    return 0;
}

25의 위치: 3
100의 위치: -1

25는 인덱스 3에서 찾았으므로 비교를 4번(인덱스 0, 1, 2, 3) 했고, 100은 배열에 없으므로 5번 전부 비교한 뒤 -1을 반환한다. 원소가 $n$개일 때 최악의 경우(찾는 값이 맨 뒤에 있거나 아예 없는 경우) 비교 횟수는 $n$번이므로 순차 탐색의 시간 복잡도는 $O(n)$이다. 정렬된 배열에서는 이진 탐색으로 $O(\log n)$까지 줄일 수 있는데, 이 내용은 05편에서 다룬 원리를 바탕으로 16편(정렬·탐색·해싱의 비교 구조)에서 자세히 다룬다.

배열의 삽입 — 원소 이동을 세어 보기

배열은 메모리가 연속되어 있으므로, 중간에 원소를 끼워 넣으려면 그 뒤에 있는 원소를 전부 한 칸씩 뒤로 밀어야 한다. 배열 {10, 20, 30, 40}(인덱스 0–3, 원소 4개, 배열 크기는 6이라 가정)의 인덱스 1 위치에 15를 삽입하는 과정을 단계별로 추적해 보자.

원소 4개 중 삽입 위치(인덱스 1) 뒤에 있는 3개(20, 30, 40)를 전부 한 칸씩 밀었으므로 이동 횟수는 3번이다. 일반화하면, 원소 $n$개인 배열의 인덱스 $k$ 위치에 삽입할 때 이동해야 하는 원소 수는 $n - k$개다. 최악의 경우(맨 앞, $k=0$)에는 $n$개를 전부 밀어야 하므로 삽입의 시간 복잡도는 $O(n)$이고, 최선의 경우(맨 뒤에 삽입, 빈 자리가 있을 때)는 이동이 전혀 없으므로 $O(1)$이다.

#include <stdio.h>
 
void insertAt(int arr[], int *n, int pos, int value) {
    for (int i = *n; i > pos; i--) {
        arr[i] = arr[i - 1];  // 뒤에서부터 한 칸씩 밀기
    }
    arr[pos] = value;
    (*n)++;
}
 
int main(void) {
    int arr[6] = {10, 20, 30, 40};
    int n = 4;
    insertAt(arr, &n, 1, 15);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

10 15 20 30 40

for 반복문이 i = 4부터 i = 2까지(즉 pos + 1인 2보다 큰 동안) 3번 실행되며, 이 반복 횟수가 바로 위 표에서 센 이동 횟수 3과 일치한다.

배열의 삭제 — 원소 이동을 세어 보기

삭제는 삽입의 반대 방향으로 원소를 당겨 오는 과정이다. 배열 {10, 15, 20, 30, 40}(원소 5개)에서 인덱스 1의 15를 삭제하는 과정을 추적해 보자.

삭제 위치(인덱스 1) 뒤에 있던 3개(20, 30, 40)를 한 칸씩 당겼으므로 이동 횟수는 3번이다. 일반화하면 원소 $n$개 중 인덱스 $k$를 삭제할 때 이동 횟수는 $n - k - 1$개이며, 최악의 경우(맨 앞 삭제)는 $O(n)$, 최선의 경우(맨 뒤 삭제)는 $O(1)$이다.

자주 틀리는 점: “배열에서 원소 하나를 삭제하는 연산 자체는 $O(1)$“이라고 오해하는 경우가 많다. 그 자리의 값을 지우는 것 자체는 $O(1)$이지만, 배열의 연속성(빈 칸이 없어야 한다는 성질)을 유지하려면 뒤 원소를 당겨야 하므로 전체 연산은 $O(n)$이다.

배열의 장단점

이 표는 07편(단순 연결리스트의 구조와 연산)에서 같은 항목을 연결리스트로 채운 표와 나란히 비교할 것이므로, 지금은 “배열은 접근이 빠른 대신 중간 삽입·삭제가 느리다”는 트레이드오프를 기억해 두면 된다.

자주 틀리는 점

• 다차원 배열 주소 계산에서 행과 열의 역할을 바꿔 계산하는 실수: C는 행 우선이므로 공식은 $(i \times \text{열의 개수} + j)$이지 $(j \times \text{행의 개수} + i)$가 아니다. 문제에서 “열 우선”이라고 명시하지 않는 한 행 우선으로 계산한다.
• 삽입·삭제의 시간 복잡도를 위치와 무관하게 하나로 단정하는 실수: 맨 뒤 삽입/삭제는 $O(1)$, 중간·맨 앞은 $O(n)$이다. “배열의 삽입은 항상 $O(n)$이다”는 최악의 경우만 말한 것이며, 위치에 따라 달라진다는 점을 문제에서 물으면 구분해서 답해야 한다.
• 배열 인덱스를 1부터 세는 실수: A[3][4]처럼 배열 선언의 숫자는 “크기”이고, 실제 유효 인덱스는 0부터 크기-1까지다.

핵심 정리

• 1차원 배열의 주소는 $\text{base} + i \times \text{size}$로 $O(1)$에 계산되며, 이것이 배열의 임의 접근이 빠른 이유다.
• 2차원 배열은 C의 행 우선 방식에서 $\text{base} + (i \times \text{열의 개수} + j) \times \text{size}$로 주소를 계산한다.
• 배열의 중간 삽입·삭제는 뒤(또는 사이) 원소를 이동해야 하므로 최악의 경우 $O(n)$이고, 맨 뒤에서의 삽입·삭제는 이동이 없어 $O(1)$이다.
• 배열은 인덱스 접근이 빠른 대신 중간 삽입·삭제가 느리고 크기 변경이 어렵다는 트레이드오프를 가진다.

마무리 복습

참고 자료

• MDN Indexed collections  — 배열과 인덱스 기반 컬렉션의 구조·성질을 정리한 참고 자료.
• 국가평생교육진흥원 과목별 평가영역  — 자료구조 과목의 범위와 평가영역을 확인할 수 있는 공식 안내.