통합 요약노트
Ch.11 고급 자료구조
Trie, Heap 심화, Segment Tree, Interval 문제
이 챕터의 내용
Trie — 문자열 검색의 끝판왕
Trie(트라이)는 문자열을 문자 단위로 저장하여 접두사 검색을 O(m) — 문자열 길이만큼 — 에 해결합니다.
해시맵은 정확한 키만 찾습니다. 'app'로 시작하는 모든 단어를 찾으려면?
Trie는 문자 하나하나를 노드로 저장합니다. 'apple', 'app', 'apt' → 'a'-'p' 경로를 공유합니다
Trie의 핵심: 공통 접두사를 공유하여 메모리를 절약하고, 접두사 검색이 O(m)에 가능
Heap 심화 — heapify부터 Two Heaps까지
heapify의 O(n) 비밀부터 시작하여, heap sort, 그리고 Two Heaps 패턴까지 마스터합니다.
n개 원소를 하나씩 insert하면 O(n log n). 하지만 heapify는 O(n)에 완성합니다
핵심 아이디어: 아래에서 위로 sift-down. 리프 노드(절반)는 이미 힙이므로 건너뜁니다
Heap Sort는 두 단계입니다: 1) heapify O(n) 2) 추출 반복 O(n log n)
Segment Tree — 구간 쿼리의 마법
Segment Tree는 build O(n), query O(log n), update O(log n) — 구간 쿼리의 만능 해결사입니다.
구간 합을 구하는 방법들을 비교해봅시다
쿼리와 업데이트가 모두 빈번할 때 Segment Tree가 빛납니다
배열 [1, 3, 5, 7, 9, 11]의 Segment Tree를 그려봅시다
Interval 문제 — 겹치는 구간 다루기
정렬 + 스캔으로 O(n log n)에 해결합니다. Interval 문제의 핵심 패턴을 배웁니다.
Interval 문제는 면접에서 매우 자주 출제됩니다
겹치는 구간을 합치는 3단계: 1) 정렬 2) 스캔 3) 병합
1,3],[2,6],[8,10],[15,18을 병합 과정을 추적합니다
면접 실전 — Trie, Two Heaps, Intervals 코딩
ATSO 프레임워크로 접근하고, 코드를 한 줄씩 작성하며 구현 감각을 익힙니다.
Trie 클래스를 구현하세요. insert, search, startsWith 메서드를 포함합니다
_find 헬퍼 메서드로 코드를 DRY하게! 면접관이 좋아하는 패턴입니다
숫자를 하나씩 추가하며 현재까지의 중간값을 반환하세요
챕터 11 종합퀴즈 — Advanced Data Structures
6라운드 퀴즈로 확실하게 정리하고 넘어갑시다!
Trie에서 'apple'을 insert한 뒤 search('app')의 결과는?
Trie의 각 노드가 가지는 두 가지 속성은?
heapify에서 sift-down을 시작하는 인덱스는?
- Trie: 접두사 검색 O(m), 자동완성의 핵심
- Heap: heapify O(n), Two Heaps로 실시간 중간값
- Segment Tree: build O(n), query/update O(log n)
- Interval: 정렬 + 스캔으로 O(n log n) 해결
핵심 용어 모음
Trie (트라이)
문자 단위로 저장하는 트리, prefix tree라고도 함
Prefix Search
접두사로 시작하는 모든 문자열을 빠르게 탐색
TrieNode
children 딕셔너리 + is_end 플래그로 구성
insert
O(m) — m은 단어 길이
search
O(m)
startsWith
O(m)
공간
O(N × m) — N개 단어, 평균 길이 m
heapify
배열 → 힙 변환, sift-down 방식으로 O(n)
sift-down
부모를 자식과 비교하며 아래로 내리는 연산
Two Heaps
max-heap + min-heap으로 중간값을 실시간 추적
시간
O(n log n) — heapify O(n) + 추출 O(n log n)
안정성
불안정 정렬 (같은 값의 순서 보장 X)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기