2What — 같은 작업, 극적으로 다른 비용
3- Python의 내장 자료구조(list, dict, set, deque)는 겉보기에 비슷한 연산을 제공하지만, 내부 구현에 따라 시간 복잡도가 완전히 다르다
4- 핵심 구분: O(1) (상수 시간) vs O(n) (선형 시간)
5- 예: list.pop(0)은 O(n), deque.popleft()는 O(1)
6- 10만 건 처리 시 이 차이는 수십 배의 실행 시간 격차로 벌어진다 (Cormen et al., 2009)
7Why — '블랙박스'로만 쓸 때 빠지는 성능 함정
8- 함정 1: 루프 안에서 list에 in 연산자 사용
9 - list의 in 연산은 O(n) — 원소를 처음부터 끝까지 순회
10 - 루프가 n번 돌면 전체 O(n^{2}) → 10만 건에서 수 초 ~ 수십 초
11 - set의 in 연산은 해시 테이블 기반 O(1) → 같은 작업이 밀리초 단위
12- 함정 2: list.pop(0)을 큐처럼 사용
13 - list는 동적 배열(dynamic array) — 앞에서 빼면 나머지 원소를 전부 왼쪽으로 시프트 → O(n)
14 - deque는 이중 연결 리스트(doubly-linked list) 기반 — 양쪽 끝 삽입/삭제가 O(1) (CPython 소스, listobject.c vs _collectionsmodule.c)
15- 함정 3: dict 키 검색을 list 순회로 대체
16 - dict는 해시 맵 — 키 조회 평균 O(1), list 순회는 O(n)
17How — CPython 내부 구현이 만드는 차이
18- CPython의 내장 자료구조는 C 레벨로 최적화되어 있다
19- list: 연속 메모리 블록에 포인터 배열 저장 → 인덱싱 O(1), 앞쪽 삽입/삭제 O(n)
20- dict: 오픈 어드레싱 해시 테이블 → 조회·삽입·삭제 평균 O(1) (Knuth, 1998)
21- set: dict와 동일한 해시 테이블 구조 (값 없이 키만 저장)
22- deque: 고정 크기 블록(64개 슬롯)의 이중 연결 리스트 → 양쪽 끝 O(1)
23실제 비용 비교 — 체감 수치
24- n = 100{,}000 기준 벤치마크 (CPython 3.11)
25 - list.pop(0) 반복: ~2.5초
26 - deque.popleft() 반복: ~0.008초 (약 300배 차이)
27 - list에서 in 검색 반복: ~6초
28 - set에서 in 검색 반복: ~0.01초 (약 600배 차이)
29- 이것은 알고리즘이 아니라 자료구조 선택만으로 발생하는 차이다
30실전 사례 — 언제 어떤 자료구조를 선택하나
31- 웹 서버 캐싱: 최근 접근 항목 관리에 dict + deque 조합 (LRU 캐시) → 조회·삽입·삭제 모두 O(1) (Python 표준 라이브러리 functools.lru_cache 구현)
32- 중복 제거 파이프라인: 수백만 로그에서 고유 IP 추출 → list로 하면 O(n^{2}), set으로 하면 O(n)
33- 실시간 집계: 스트리밍 데이터의 빈도 집계 → dict(또는 Counter)로 O(1) 업데이트, list 순회 방식은 확장 불가
34- 큐/BFS 탐색: deque를 사용해야 O(V + E) 보장, list.pop(0)이면 O(V \times E)로 악화
35핵심 원칙 정리
36- "자료구조를 모르면 Python을 아는 것이 아니라 Python의 표면을 아는 것이다"
37- 같은 언어, 같은 문법이라도 내부 구현을 이해하면 코드 한 줄의 교체로 수십~수백 배 성능 향상이 가능하다 (Skiena, 2020)
38- 빅오 표기법은 이론이 아니라 실무에서 매일 마주치는 비용 계산 도구이다