동적 배열: Python list 는 어떻게 자라나

"날것 배열은 크기가 고정이야. Python 리스트는 안 그런 척해 — 그 약속을 지키려고 쓰는 트릭이 네 도구함에서 가장 조용히 영리한 것 중 하나야."

리스트가 푸는 문제

저수준 배열은 고정 블록이야 — 크기를 선언하면 거기 묶여. 근데 최종 크기를 미리 아는 일은 드물어. 동적 배열은 그 한계를 감춰: append 하면 자라서, 무한한 것처럼 느껴져. Python 의 list 가 동적 배열이야 (C++ 은 vector, Java 는 ArrayList — 어디서나 같은 아이디어).

비밀은, 분할 상환 분석에서 이미 만난 거: 리스트는 실제 길이 (length) 보다 큰 여유 공간 (용량, capacity) 을 가진 backing 배열을 둬. append 는 여유 공간에 공짜로 떨어져 (O(1)). 여유가 떨어지면, 리스트가 더 큰 블록을 할당하고 — 대략 두 배 — 전부 복사하고 (O(n)), 다시 여유 공간을 가져. 두 배 하기가 지수적으로 드물어져서, append 는 분할 상환 O(1) 이야.

길이는 용량이 아니야

이게 모든 걸 설명하는 구분이야: len(lst) 는 저장한 항목 수고; 용량은 다음 재할당 전까지 담을 수 있는 수야. Python 에서 용량을 직접 보진 못하지만, 예약된 바이트로 볼 수 있어. 그게 존재한다는 걸 아는 게 "append 가 보통 즉시인데 가끔 멈춤" 을 안 신비롭게 만들어.

동적 배열 = 고정 배열 + 여유 용량 + 두 배 규칙. 길이는 저장한 것; 용량은 다음 O(n) 재성장 전까지 맞는 것. 그 간극이 append 를 분할 상환 O(1) 으로 만들어.

연산과 그 진짜 비용

리스트가 연속이라, 각 연산의 비용은 "뭐가 움직여야 하나?" 에서 바로 떨어져:

lst[i] 읽기/쓰기 — O(1), 주소 산술.
lst.append(x) / lst.pop() — 분할 상환 O(1), 끝에서 일, 아무것도 안 밀려.
lst.insert(0, x) / lst.pop(0) — O(n), 그 자리 뒤 전부가 밀려.
x in lst — O(n), 선형 훑기 (Complexity 트랙의 숨은 반복문 함정).
lst[a:b] 슬라이스 — O(b−a), 그 범위를 새 리스트로 복사.

피파의 고백

난 평범한 리스트로 큐를 만들고 lst.pop(0) 로 dequeue 하곤 했어. 작은 테스트에선 완벽히 돌고 진짜 데이터에선 조용히 내 O(n) 반복문을 O(n²) 으로 바꿨어, 매 pop(0) 가 리스트 전체를 왼쪽으로 밀었거든. 아빠가 앞-pop 을 O(1) 으로 하는 collections.deque 를 보여줬어. 같은 아이디어, 맞는 구조. 리스트가 틀린 게 아니라 — 내가 그 비싼 끝을 공짜인 것처럼 쓴 거야.

Code

길이 vs 용량, 그리고 연산 비용·python

import sys

# 길이 vs 용량: 길이가 매끄럽게 오르는 동안 예약 바이트가 점프하는 걸 봐.
lst = []
for i in range(9):
    print(f"len={len(lst)}  reserved_bytes={sys.getsizeof(lst)}")
    lst.append(i)
# 바이트 수가 특정 길이에서 점프 (재할당) — 그게 용량이 두 배로
# 커지는 거고, len 은 매번 1 씩만 똑딱.

# 비용 치트시트, 시연:
lst = list(range(5))
lst.append(99)        # 분할 상환 O(1) — 끝의 여유 용량에 떨어짐
lst.pop()             # O(1) — 끝에서 제거, 아무것도 안 밀림
lst.insert(0, -1)     # O(n) — 인덱스 0 열려고 모든 원소 오른쪽으로 밀림
lst.pop(0)            # O(n) — 간극 메우려 모든 원소 왼쪽으로 밀림
print(3 in lst)       # O(n) — 선형 훑기, 리스트엔 지름길 없음
print(lst[1:4])       # O(k) — 그 슬라이스를 새 리스트로 복사

Exercise

항목을 엄격히 도착 순으로 처리해야 해: 뒤에 추가, 앞에서 제거, 수백만 번. 이걸 리스트랑 pop(0) 으로 하면 왜 전체가 O(n²) 인지 스케치하고, O(n) 으로 만드는 구조를 대봐. 보너스: Python 리스트의 어느 끝이 싼 끝이고 왜?

Hint

각 pop(0) 이 O(n) 이고 n 번 하니 → O(n²). collections.deque 는 양 끝 O(1). 리스트의 싼 끝은 뒤 (append/pop) 야, 거긴 아무것도 안 밀려도 되니까.

리스트가 푸는 문제

길이는 용량이 아니야

연산과 그 진짜 비용

피파의 고백

Code

External links

Exercise

Progress

댓글 0