🌳
트리
문자열 검색·자동완성·접두사
강의 19: 트라이 (Trie / Prefix Tree)
여러 문자열을 빠르게 검색·접두사 처리하는 트라이 자료구조를 익힙니다.
트라이트리문자열
소요 시간
⏱ 약 1시간
난이도
📊 중급
선수 조건
🎯 단원 17
결과물
여러 문자열을 빠르게 검색·접두사 처리하는 트라이 자료구조를 익힙니다.
이 강의에서 배우는 것
- 1트라이의 노드 구조(children 딕셔너리, is_end 플래그)를 이해하고 Python으로 구현할 수 있다.
- 2insert/search/starts_with를 O(m)에 구현하고, 자동 완성 기능을 작성할 수 있다.
- 3XOR 트라이를 이용해 배열에서 최대 XOR 쌍을 O(n × 32) 시간에 구할 수 있다.
소개
트라이(Trie)는 **문자열을 저장하고 검색하는 데 특화된 트리** 자료구조입니다. "Retrieval"의 중간 글자에서 이름을 따왔으며, **접두사 트리(Prefix Tree)** 라고도 합니다.
실생활 응용:
- **자동 완성(Autocomplete)**: 검색 엔진, IDE 코드 완성
- **맞춤법 검사(Spell Check)**: 단어 존재 여부 O(m) 확인
- **IP 라우팅**: 최장 접두사 매칭
- **전화번호 일관성**: 한 번호가 다른 번호의 접두사인지 확인
text
해시셋 vs 트라이
─────────────────────────────────────────────────────────────
기능 해시셋 트라이
─────────────────────────────────────────────────────────────
단어 검색 O(m) O(m)
단어 삽입 O(m) O(m)
접두사 검색 O(n×m) O(m) ← 트라이 강점!
자동 완성 O(n×m) O(m + 결과 수)
공통 접두사 길이 O(n×m) O(m)
공간 O(n×m) O(알파벳크기 × 최대길이 × n)
─────────────────────────────────────────────────────────────
m = 단어 길이, n = 단어 수핵심 개념
트라이 노드 구조
python
class TrieNode:
def __init__(self):
self.children: dict[str, TrieNode] = {}
self.is_end: bool = False # 단어 끝 표시
self.count: int = 0 # (선택) 해당 접두사를 가진 단어 수텍스트 아트: 트라이 예시
text
단어: ["apple", "app", "apt", "bat", "ball"]
(루트)
/ \
a b
| |
p a
/ \ / \
p t t l
| | | |
l (끝) (끝) l
| |
e (끝)
|
(끝) ← "apple" 끝
↑
"app" 끝 표시도 p 노드에
경로: root → a → p → p (is_end=True: "app") → l → e (is_end=True: "apple")복잡도 정리
text
┌─────────────────┬────────────────────┬────────────────────────────────┐
│ 연산 │ 시간 복잡도 │ 설명 │
├─────────────────┼────────────────────┼────────────────────────────────┤
│ insert(word) │ O(m) │ m = 단어 길이 │
│ search(word) │ O(m) │ │
│ starts_with(p) │ O(m) │ p = 접두사 길이 │
│ autocomplete │ O(m + 결과 수) │ DFS로 모든 완성 탐색 │
│ 삭제 │ O(m) │ │
└─────────────────┴────────────────────┴────────────────────────────────┘
공간 복잡도:
- 최악: O(alphabet_size × max_len × n)
- alphabet_size = 26 (소문자 영문)
- 딕셔너리 사용 시: O(total_chars) — 실제 저장된 문자 수XOR 트라이 개념
text
정수를 이진수 비트로 트라이에 저장:
32 = 0...0 100000 (31비트)
XOR 최대화: 각 비트에서 현재 비트와 반대 방향으로 이동하면 XOR 최대
비트 1 → 0 방향 탐색 (XOR = 1)
비트 0 → 1 방향 탐색 (XOR = 1)예제로 보기
| 파일 | 내용 |
|---|---|
| `src/01_trie_basic.py` | Trie: insert, search, starts_with |
| `src/02_trie_autocomplete.py` | 자동 완성 제안 |
| `src/03_trie_count.py` | 접두사 카운트, 단어 빈도 |
| `src/04_trie_applications.py` | 최장 공통 접두사, XOR 트라이 |
자주 하는 실수
- **is_end 플래그 누락**: 단어 삽입 후 마지막 노드에 `is_end = True` 표시를 빠뜨리면 search가 항상 False 반환
- **starts_with vs search 혼동**: `starts_with`는 접두사만 존재하면 True, `search`는 정확히 그 단어여야 True
- **삭제 시 공유 경로 보존**: 다른 단어와 공유하는 노드를 삭제하면 안 됨 ("app"과 "apple" 공유 → "app" 삭제 시 "apple"도 손상 가능)
- **XOR 트라이 비트 범위**: 정수 최댓값에 따라 비트 수 결정 필요 (보통 31비트 또는 32비트)
- **메모리 과다 사용**: 배열 기반(`children = [None] * 26`) 트라이는 희소할 경우 낭비 — 딕셔너리 사용 권장
정리
- 트라이는 **접두사 검색 O(m)**이 핵심 강점
- 단어 검색/삽입/삭제 모두 O(m) — 단어 수 n과 무관
- 공간은 최악 O(alphabet × max_len × n)이지만 딕셔너리 기반은 실제 사용 문자 수에 비례
- **XOR 트라이**: 비트 트라이로 최대 XOR 쌍을 O(n × 32)에 해결
직접 해 보기
- 트라이에서 단어 삭제 함수 구현 (참조 카운트 활용)
- 두 트라이를 합치는 함수 작성
- 트라이로 가장 짧은 고유 접두사 찾기 (예: "apple"의 고유 접두사 = "ap" if "apt" 없으면 "ap")
과제
📂 `homework/README.md` 참조
- 백준 14425 (문자열 집합) — Silver III
- 백준 5052 (전화번호 목록) — Gold IV