동작 원리

이 장에서는 각 구조를 작은 예제로 따라가며, 연산마다 메모리에서 정확히 무엇이 움직이는지 살펴봅니다.

동적 배열이 자라는 과정

동적 배열은 size(사용 중인 칸)와 capacity(확보한 칸)를 따로 기억합니다. size == capacity 인 상태에서 추가하면 두 배 크기의 블록을 새로 잡고, 기존 항목을 복사한 다음 새 항목을 씁니다. 용량 1에서 시작해 아홉 번 추가하면 다음과 같습니다.

아홉 번 추가하는 동안 복사는 1 + 2 + 4 + 8 = 15번으로, 추가 한 번당 두 번이 안 됩니다. 한 번의 추가가 O(n)일 때가 있어도 전체로 보면 분할 상환 O(1)인 이유입니다. 아래 시뮬레이션은 추가 횟수에 따른 복사 횟수를 셉니다.

def count_copies(n, growth=2):
    size, capacity, copies = 0, 1, 0
    for _ in range(n):
        if size == capacity:
            copies += size            # 모든 항목을 새 블록으로 옮김
            capacity *= growth
        size += 1
    return copies

for n in (9, 1_000, 1_000_000):
    print(n, count_copies(n), round(count_copies(n) / n, 2))
# 추가 한 번당 복사 횟수는 2보다 작게 유지됩니다

맨 앞에 넣는 경우는 다릅니다. 기존 항목이 모두 오른쪽으로 한 칸씩 밀리므로, list.insert(0, x) 는 가끔이 아니라 매번 O(n)입니다.

연결 리스트에 끼워 넣기

단일 연결 리스트 A -> B -> D 는 노드 세 개로 이루어지고, 각 노드는 next 참조를 가집니다. B 뒤에 C 를 넣으려면 다음과 같이 합니다.

1. 노드 C 를 만듭니다.
2. C.next = B.next 로 설정합니다(C 가 D 를 가리킴).
3. B.next = C 로 설정합니다.

리스트 길이와 상관없이 참조 두 개만 바뀝니다. 2와 3의 순서가 중요합니다. 3을 먼저 하면 D 를 가리키던 유일한 참조를 잃어버립니다. 다만 처음에 B 를 찾으려면 머리부터 걸어가야 하므로 그 부분은 O(n)입니다.

스택으로 괄호 검사하기

중첩된 구조라면 스택이 자연스러운 도구입니다. ([]{}) 가 균형 잡혔는지 보려면 여는 괄호는 넣고, 닫는 괄호를 만나면 꺼내서 짝을 비교합니다.

꺼낼 때마다 짝이 맞았고 마지막에 스택이 비었으므로 균형 잡힌 입력입니다.

PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(text):
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack.pop() != PAIRS[ch]:
                return False
    return not stack

print(balanced("([]{})"), balanced("(]"), balanced("(("))  # True False False

원형 버퍼로 만든 큐

고정 배열 위의 큐는 인덱스 두 개를 씁니다. head 는 다음에 꺼낼 항목, tail 은 다음 빈칸입니다. 둘 다 앞으로만 움직이고 % capacity 로 처음으로 돌아가므로 항목을 밀 일이 없습니다. 용량이 4일 때입니다.

e 를 넣을 때 tail이 0번 칸으로 돌아왔습니다. 버퍼가 가득 차면 늘어나는 버전은 큐 순서대로 항목을 더 큰 배열에 옮기고 head 를 0으로 되돌립니다.

분리 연결법 해시 테이블

해시 테이블은 버킷 배열을 가집니다. 키를 저장할 때 hash(key) % 버킷 수 를 계산해 그 버킷에 쌍을 넣습니다. 분리 연결법(separate chaining)에서는 버킷마다 작은 리스트를 두고, 충돌한 키는 그 리스트를 함께 씁니다. 버킷 8개, 해시값이 자기 자신인 정수 키로 보겠습니다.

3, 11, 19가 충돌했습니다. 19를 찾으면 버킷 3으로 간 뒤 항목 세 개를 훑습니다. 적재율은 4 / 8 = 0.5입니다. 적재율이 0.75 같은 기준을 넘으면 버킷 수를 두 배로 늘리고 모든 쌍을 다시 넣습니다. 버킷 번호가 버킷 수에 따라 달라지기 때문입니다.

def place(keys, bucket_count):
    buckets = [[] for _ in range(bucket_count)]
    for key in keys:
        buckets[hash(key) % bucket_count].append(key)
    return {i: b for i, b in enumerate(buckets) if b}

keys = [3, 11, 6, 19]
print(place(keys, 8))   # {3: [3, 11, 19], 6: [6]}
print(place(keys, 16))  # {3: [3, 19], 6: [6], 11: [11]}

버킷을 16개로 늘리자 긴 사슬이 나뉘었습니다. 좋은 해시 함수와 일정 이하로 유지되는 적재율이 사슬을 짧게 지켜 주며, 평균 O(1)은 여기서 나옵니다.

정리

동적 배열은 가끔 하는 복사로 싼 추가를 얻고, 연결 리스트는 끼워 넣을 때 참조 두어 개만 바꾸며, 스택과 원형 버퍼 큐는 끝만 건드리고, 해시 테이블은 버킷을 계산한 뒤 짧은 사슬만 훑습니다. 종이에 한 번 따라 그려 보면 복잡도 숫자를 외우지 않아도 자연스럽게 이해됩니다.