컴퓨터공학 300 주제 시리즈의 041번째 글이다. 전체 지도는 여기.

한 줄 요약

배열은 같은 크기의 칸을 메모리에 빈틈없이 늘어놓은 것이고, 동적 배열은 칸이 모자라면 더 큰 배열을 새로 잡아 옮겨 담는 방식으로 “끝에 추가”를 분할 상환 O(1) 로 만든 배열이다.

왜 필요한가

자료구조 파트를 배열로 시작하는 이유는 간단하다. 거의 모든 자료구조가 결국 배열 위에 지어지거나, 배열과 비교해서 평가받는다. 해시 테이블의 버킷은 배열이고, 힙은 배열에 담긴 트리이고, 원형 큐는 배열의 양 끝을 이어 붙인 것이다. 연결 리스트를 배울 때도 “배열보다 무엇이 낫고 무엇이 못한가”를 묻게 된다.

그리고 실무 코드에서 가장 많이 쓰는 컨테이너도 배열이다. 파이썬의 list, 자바의 ArrayList, C++ 의 std::vector, 러스트의 Vec, 고의 슬라이스가 모두 동적 배열이다. 이 컨테이너들이 어떤 연산에 빠르고 어떤 연산에 느린지 모르면, 루프 안에서 list.pop(0) 을 부르는 식의 코드가 생긴다. 데이터가 작을 땐 티가 안 나다가, 백만 건이 되면 몇 초가 몇 분이 된다.

핵심 개념

정적 배열: 주소 계산 한 번이면 끝

배열은 시작 주소 base 와 원소 크기 s 만 알면 i 번째 원소의 주소를 바로 계산할 수 있다.

주소(i) = base + i × s

base
 │
 ▼
┌────┬────┬────┬────┬────┬────┐
│ a0 │ a1 │ a2 │ a3 │ a4 │ a5 │   (원소 하나 = s 바이트)
└────┴────┴────┴────┴────┴────┘
  0    1    2    3    4    5

곱셈 하나와 덧셈 하나다. 그래서 인덱스로 접근하는 비용은 배열 길이와 상관없이 O(1) 이다. 이것을 임의 접근(random access) 이라고 부른다.

연속 배치에는 숨은 이득도 있다. CPU 는 메모리를 바이트 단위가 아니라 캐시 라인 단위로 가져온다. a0 을 읽으면 a1, a2 도 함께 캐시에 올라올 가능성이 크다. 배열을 앞에서부터 훑는 루프가 같은 원소 수의 연결 리스트를 훑는 루프보다 대체로 빠른 이유가 여기에 있다. 점근 표기로는 둘 다 O(n) 이지만 상수가 다르다.

대가도 있다. 중간에 끼워 넣거나 빼려면 뒤쪽 원소를 전부 한 칸씩 밀거나 당겨야 한다.

연산 비용 이유
a[i] 읽기·쓰기 O(1) 주소 계산
맨 끝에 추가·삭제 O(1) (동적 배열은 분할 상환) 밀 원소가 없음
맨 앞·중간에 삽입·삭제 O(n) 뒤쪽을 모두 이동
값으로 찾기 (정렬 안 됨) O(n) 하나씩 비교
값으로 찾기 (정렬됨) O(log n) 이진 탐색

정적 배열의 한계: 크기를 미리 정해야 한다

C 의 int a[100]; 처럼 정적 배열은 만들 때 크기가 정해진다. 그런데 프로그램은 대부분 데이터가 몇 개 들어올지 모른다. 너무 크게 잡으면 메모리가 낭비되고, 작게 잡으면 넘친다. 동적 배열은 이 문제를 “꽉 차면 더 큰 데로 이사”로 푼다.

동적 배열: 용량과 길이를 따로 관리

동적 배열은 두 숫자를 들고 있다.

  • 길이(length, n): 실제로 들어 있는 원소 수
  • 용량(capacity, cap): 지금 잡아 둔 칸 수

n < cap 이면 추가는 빈칸에 쓰기만 하면 된다. n == cap 이면 더 큰 배열(예: 2배)을 새로 잡고, 기존 원소를 전부 복사한 다음, 옛 배열을 버린다.

cap=4  [a][b][c][d]          ← 꽉 참, e 추가 요청
cap=8  [a][b][c][d][ ][ ][ ][ ]  ← 새로 잡고 4개 복사
       [a][b][c][d][e][ ][ ][ ]  ← e 쓰기

분할 상환(amortized) O(1)

복사가 일어나는 추가는 O(n) 이다. 그런데도 “끝에 추가는 O(1)” 이라고 말하는 근거가 분할 상환 분석이다. 용량을 2배씩 늘리면, n 개를 추가하는 동안 복사가 일어나는 시점은 용량이 1, 2, 4, 8, … 일 때다. 복사한 원소 수의 합은

1 + 2 + 4 + … + 2^k  <  2 × 2^k  ≤  2n  (대략)

이다. n 번 추가에 총 복사가 2n 미만이니, 한 번당 평균 2회 미만의 복사다. 각 연산은 들쭉날쭉하지만 긴 연산 열 전체로 보면 한 번에 상수 비용이라는 뜻이다. 평균 시간(입력 분포에 대한 기댓값)과는 다른 개념이다. 분할 상환은 확률을 쓰지 않는다. 최악의 연산 순서에서도 총합이 보장된다.

중요한 조건이 하나 있다. 용량을 곱하기로 늘려야 한다. 매번 10칸씩 더하기로 늘리면 복사 총량이 10 + 20 + 30 + … 로 O(n²) 이 되어 한 번당 O(n) 이 된다. 배율은 꼭 2 일 필요는 없다. 1.5 든 1.125 든 1 보다 큰 상수 배면 분할 상환 O(1) 은 유지되고, 배율이 작을수록 메모리 낭비가 줄어드는 대신 복사가 잦아진다.

실제 구현이 쓰는 정확한 배율은 언어마다 다르고, 대개 명세로 약속하지 않는다. 자바 ArrayList 문서는 “성장 정책의 세부는 추가가 분할 상환 상수 시간이라는 사실 외에는 명시하지 않는다”고 적는다(Java SE 21 ArrayList). 러스트 Vec 문서도 용량과 길이의 차이, 그리고 with_capacity 로 미리 잡아 두는 법을 따로 설명한다(Rust Vec).

줄일 때는 조심

삭제로 원소가 줄 때도 용량을 줄이고 싶을 수 있다. 하지만 “절반 이하가 되면 절반으로 줄인다”고 하면, 경계에서 추가와 삭제가 번갈아 들어올 때마다 늘리고 줄이기를 반복해 매번 O(n) 이 된다. 교과서적인 해법은 “4분의 1 이하가 되면 절반으로” 처럼 늘리는 기준과 줄이는 기준 사이에 간격을 두는 것이다.

고의 슬라이스: 길이·용량이 겉으로 보인다

고의 슬라이스는 이 구조가 문법에 그대로 드러난다. 슬라이스는 “배열 포인터, 길이, 용량” 세 값으로 된 헤더이고, append 가 용량을 넘으면 새 배열을 잡는다. 그래서 같은 배열을 공유하던 두 슬라이스가 append 이후 서로 다른 배열을 가리키게 될 수 있다(Go Slices: usage and internals). 동적 배열의 “이사”가 사용자 코드의 버그로 번지는 대표적인 장면이다.

직접 해 보기

용량을 2배로 늘리는 동적 배열을 직접 만들고, 원소를 옮긴 횟수를 세어 본다.

class DynamicArray:
    def __init__(self):
        self.cap = 1
        self.n = 0
        self.buf = [None] * self.cap
        self.copies = 0          # 원소를 옮긴 총 횟수

    def append(self, x):
        if self.n == self.cap:   # 꽉 찼으면 두 배로
            self._grow(self.cap * 2)
        self.buf[self.n] = x
        self.n += 1

    def _grow(self, new_cap):
        new_buf = [None] * new_cap
        for i in range(self.n):
            new_buf[i] = self.buf[i]
            self.copies += 1
        self.buf, self.cap = new_buf, new_cap

    def __getitem__(self, i):
        if not 0 <= i < self.n:
            raise IndexError(i)
        return self.buf[i]

for N in (1_000, 1_000_000):
    a = DynamicArray()
    for i in range(N):
        a.append(i)
    print(f"N={N:>9,}  cap={a.cap:>9,}  copies={a.copies:>9,}  copies/N={a.copies/N:.2f}")

파이썬 3.12 에서 실행한 결과다.

N=    1,000  cap=    1,024  copies=    1,023  copies/N=1.02
N=1,000,000  cap=1,048,576  copies=1,048,575  copies/N=1.05

백만 개를 넣어도 원소 하나당 복사는 1회 남짓이다. 위에서 계산한 “2회 미만”과 맞는다.

이번엔 진짜 파이썬 list 의 용량이 어떻게 늘어나는지 sys.getsizeof 로 엿본다. 64비트 CPython 에서 포인터 한 칸은 8바이트라고 보고 칸 수로 환산했다.

import sys
l = []; prev = sys.getsizeof(l); caps = []
for i in range(70):
    l.append(i); s = sys.getsizeof(l)
    if s != prev:
        caps.append((len(l), (s - sys.getsizeof([])) // 8)); prev = s
print(caps)

[(1, 4), (5, 8), (9, 16), (17, 24), (25, 32), (33, 40), (41, 52), (53, 64), (65, 76)]

2배가 아니라 대략 1.125배에 작은 상수를 더하는 식으로 늘어난다. 이 수치는 CPython 3.12 구현의 동작일 뿐 언어 명세가 아니다. 버전이 바뀌면 달라질 수 있다.

마지막으로 앞에서 빼기와 끝에서 빼기를 비교한다.

import timeit
setup = "l = list(range(100_000))"
print("pop()  ", timeit.timeit("l.append(0); l.pop()", setup, number=10_000))
print("pop(0) ", timeit.timeit("l.insert(0,0); l.pop(0)", setup, number=10_000))

이 글을 쓰며 실행한 환경에서는 pop() 쪽이 약 0.001초, pop(0) 쪽이 약 0.78초였다. 절대값은 기계마다 다르지만, 수백 배 차이가 나는 경향은 같다. 파이썬 공식 위키의 시간 복잡도 표도 list 의 pop 중간 삭제와 insert 를 O(n) 으로 적는다(Python Wiki TimeComplexity). 앞에서 자주 빼야 하면 collections.deque 를 쓴다. 이건 덱 편에서 다룬다.

현업에서는

  • 미리 용량 잡기. 넣을 개수를 알면 ArrayList(int initialCapacity), Vec::with_capacity, make([]T, 0, n) 으로 미리 잡는다. 복사를 없애는 것보다 큰 효과는 메모리 사용량이 2배 가까이 튀는 순간을 없애는 것이다. 이사하는 동안에는 옛 배열과 새 배열이 동시에 살아 있기 때문이다.
  • 메모리 한도와 순간 최대치. 쿠버네티스 파드에 메모리 limit 을 걸어 두면, 큰 리스트가 용량을 늘리는 순간에 잠깐 두 배를 먹다가 OOMKilled 되는 일이 생긴다. 평소 사용량 그래프만 보면 여유가 있어 보여서 원인을 찾기 어렵다. 노드 메모리가 작은 홈랩 클러스터에서는 limit 을 빠듯하게 잡기 쉬워 더 잘 드러난다.
  • 큐로 오용된 리스트. 작업 목록을 list 에 넣고 pop(0) 으로 꺼내는 코드는 리뷰에서 흔히 잡힌다. 데이터가 커지면 전체 처리 시간이 O(n²) 이 된다.
  • 슬라이스 공유 버그. 고에서 함수 인자로 받은 슬라이스에 append 한 뒤 원래 슬라이스도 바뀌었다고 가정하는 버그는 용량 개념을 모르면 재현 조건조차 이해하기 어렵다.

확인 문제

  1. 원소 크기가 4바이트인 배열의 시작 주소가 1000 일 때, 인덱스 7 원소의 주소는?
  2. 동적 배열의 용량을 “가득 차면 100칸 추가”로 늘리면 n 번 추가의 총비용은 어떤 차수가 되는가?
  3. 분할 상환 O(1) 과 평균 O(1) 은 무엇이 다른가?
  4. 용량을 “절반 이하면 절반으로 줄인다”고 하면 어떤 연산 순서에서 문제가 생기는가?
  5. 배열과 연결 리스트를 둘 다 처음부터 끝까지 훑는 루프가 똑같이 O(n) 인데, 배열 쪽이 대체로 빠른 이유는?

풀이

  1. 1000 + 7 × 4 = 1028.
  2. 복사량이 100 + 200 + … ≈ n²/200 이므로 O(n²). 한 번당 분할 상환 O(n) 이다.
  3. 평균은 입력이나 난수에 대한 기댓값이다. 분할 상환은 확률 없이, 어떤 연산 순서든 총비용을 연산 수로 나눈 상한이다.
  4. 용량 경계에서 추가 하나, 삭제 하나를 반복하면 늘리기와 줄이기가 번갈아 일어나 매번 O(n) 복사가 생긴다. 줄이는 기준을 4분의 1 로 낮추면 피할 수 있다.
  5. 연속 배치라 캐시 라인 하나에 여러 원소가 함께 올라오고, 하드웨어 프리페치도 잘 맞는다. 연결 리스트는 노드가 흩어져 있어 캐시 미스가 잦다.

더 읽을거리 (References)