연속 메모리와 배열 인덱싱 O(1)

이 토픽을 마치면

배열이 왜 인덱스 접근이 O(1)인지 수학적으로 설명할 수 있고, 연속 메모리의 장단점을 이해하며, 배열과 연결 리스트의 성능 차이를 파악합니다.

배열은 왜 빠른가

python

numbers = [10, 20, 30, 40, 50]
print(numbers[3])  # 40 — 즉시 접근!

5개든 500만 개든, 인덱스로 접근하는 시간은 항상 같습니다. 이것이 O(1) — 상수 시간 접근입니다.

왜 그럴까요? 배열은 메모리에 연속으로 저장되기 때문입니다.

연속 메모리 — 배열의 비밀

text

메모리 주소:  1000  1004  1008  1012  1016
값:          [10]  [20]  [30]  [40]  [50]
인덱스:        0     1     2     3     4

배열의 각 원소는 메모리에서 빈틈 없이 나란히 저장됩니다. 각 정수가 4바이트라면:

numbers[0] → 주소 1000
numbers[1] → 주소 1004
numbers[2] → 주소 1008
numbers[3] → 주소 1012

인덱싱 공식

text

원소의 주소 = 시작 주소 + (인덱스 × 원소 크기)

numbers[3] = 1000 + (3 × 4) = 1012

이 계산은 덧셈 1번, 곱셈 1번입니다. 배열 크기가 5개든 5억 개든 동일합니다. 따라서 O(1)입니다.

연결 리스트와 비교

연결 리스트는 각 노드가 다음 노드의 주소를 저장합니다. 메모리에 흩어져 있습니다.

text

메모리:  [10|→1500]  ...  [20|→2300]  ...  [30|→1800]  ...  [40|→2100]

3번째 원소를 찾으려면:
  0번 노드(1000) → 포인터 따라감
  1번 노드(1500) → 포인터 따라감
  2번 노드(2300) → 포인터 따라감
  3번 노드(1800) ← 여기!

3번째를 찾으려면 0번부터 하나씩 따라가야 합니다. n번째를 찾으려면 n번 이동 → O(n).

연산	배열	연결 리스트
인덱스 접근	O(1)	O(n)
앞에 삽입	O(n) — 전체 이동	O(1)
중간 삽입	O(n) — 뒤를 이동	O(1) — 포인터만 변경
끝에 추가	O(1) (공간 있으면)	O(1) (tail 포인터 있으면)
검색 (정렬 안 됨)	O(n)	O(n)

Python 리스트의 실체

Python의 list는 C의 배열과 다릅니다. 포인터의 배열입니다.

text

Python list:  [ptr0][ptr1][ptr2][ptr3]
                ↓     ↓     ↓     ↓
              [10]  ["hi"] [3.14] [[1,2]]

포인터(주소)는 크기가 일정(64비트 시스템에서 8바이트)하므로, 포인터 배열 자체는 연속 메모리입니다. 인덱싱 공식이 여전히 적용되어 O(1)입니다.

python

# Python list — 다양한 타입 저장 가능 (포인터 배열이므로)
mixed = [42, "hello", 3.14, [1, 2, 3]]
print(mixed[2])  # 3.14 — O(1)

하지만 실제 데이터는 메모리 곳곳에 흩어져 있으므로, C 배열보다 캐시 효율이 낮습니다.

NumPy 배열 — 진짜 연속 메모리

python

import numpy as np

# NumPy는 C 배열처럼 데이터를 연속 저장
arr = np.array([1, 2, 3, 4, 5], dtype=np.int32)
# 메모리: [00000001 00000002 00000003 00000004 00000005]
#         4바이트씩 빈틈없이 연속

NumPy가 Python list보다 수십 배 빠른 이유 중 하나가 이 연속 메모리 레이아웃입니다.

캐시 친화성

CPU는 메모리에서 데이터를 가져올 때, 요청한 주소 주변의 데이터도 함께 **캐시 라인(보통 64바이트)**에 로드합니다.

text

배열 순차 접근:
  arr[0] 접근 → 캐시에 arr[0]~arr[15] 로드
  arr[1] 접근 → 캐시 히트! (이미 로드됨)
  arr[2] 접근 → 캐시 히트!
  ...

연결 리스트 접근:
  node0 접근 → 캐시에 주변 로드
  node1 접근 → 다른 주소! 캐시 미스 → 메모리에서 다시 로드
  node2 접근 → 또 다른 주소! 캐시 미스
  ...

배열은 연속이므로 캐시 히트율이 높고, 연결 리스트는 흩어져 있으므로 캐시 미스가 잦습니다. 현대 CPU에서 캐시 미스는 캐시 히트보다 100배 이상 느립니다.

배열의 한계 — 삽입과 삭제

text

배열 중간에 삽입 (인덱스 2에 25 삽입):

Before: [10][20][30][40][50]
                 ↓
Step 1: [10][20][  ][30][40][50]  ← 30,40,50을 한 칸씩 뒤로 이동
Step 2: [10][20][25][30][40][50]  ← 빈 자리에 25 삽입

뒤의 원소들을 모두 이동해야 하므로 O(n)입니다. 삭제도 마찬가지 — 빈 자리를 메우기 위해 앞으로 이동합니다.

2차원 배열의 메모리 레이아웃

text

Row-major (C, Python, NumPy 기본):
[[1, 2, 3],     메모리: [1][2][3][4][5][6]
 [4, 5, 6]]     → 행 순서로 저장

Column-major (Fortran, MATLAB):
[[1, 2, 3],     메모리: [1][4][2][5][3][6]
 [4, 5, 6]]     → 열 순서로 저장

python

import numpy as np

arr = np.array([[1, 2, 3], [4, 5, 6]])

# C order (row-major, 기본)
print(arr.flags['C_CONTIGUOUS'])  # True

# Fortran order
arr_f = np.asfortranarray(arr)
print(arr_f.flags['F_CONTIGUOUS'])  # True

행 방향 순회가 많으면 Row-major가, 열 방향 순회가 많으면 Column-major가 캐시 효율적입니다. NumPy는 기본 C order(Row-major)를 사용합니다. 이것이 행 방향 연산(axis=1)이 열 방향 연산(axis=0)보다 종종 빠른 이유입니다 — 메모리 접근 패턴이 캐시에 유리하기 때문입니다.

동적 배열 — 크기가 늘어나는 배열

배열은 크기가 고정입니다. Python list는 동적 배열로, 꽉 차면 더 큰 배열을 할당하고 복사합니다.

python

import sys

items = []
prev_size = 0
for i in range(20):
    items.append(i)
    size = sys.getsizeof(items)
    if size != prev_size:
        print(f"len={len(items):2d}, capacity changed: {prev_size} → {size} bytes")
        prev_size = size

# len= 1, capacity changed: 56 → 88 bytes
# len= 5, capacity changed: 88 → 120 bytes
# len= 9, capacity changed: 120 → 184 bytes
# len=17, capacity changed: 184 → 248 bytes

Python은 보통 현재 크기의 1.125배 + 상수만큼 여유 공간을 확보합니다. 매번 1칸씩 늘리면 매번 전체를 복사해야 하지만(O(n)), 배수로 늘리면 **분할 상환 O(1)**이 됩니다.

핵심 정리

개념	정리
연속 메모리	원소가 빈틈 없이 나란히 저장
O(1) 인덱싱	주소 = 시작 + (인덱스 × 크기). 배열 크기와 무관
캐시 친화성	연속 메모리 → CPU 캐시 히트율 높음 → 빠름
Python list	포인터의 배열. 인덱싱은 O(1)이지만 캐시 효율은 낮음
NumPy	데이터를 연속 저장. C 배열과 유사한 성능
동적 배열	꽉 차면 배수로 확장. 분할 상환 O(1) append

배열이 O(1)인 이유는 "연속 메모리 + 곱셈 한 번"이라는 단순한 수학입니다. 이 원리를 이해하면, 왜 NumPy가 Python list보다 빠른지, 왜 데이터베이스가 인덱스를 쓰는지, 왜 캐시 최적화가 중요한지 자연스럽게 연결됩니다.

실전 요약: 인덱스 접근이 많으면 배열, 삽입/삭제가 많으면 연결 리스트. Python list는 대부분의 경우 적절하지만, 수치 계산에서는 NumPy를 쓰는 것이 수십 배 빠릅니다 — 진짜 연속 메모리이기 때문입니다.