Ch.11 고급 자료구조
Trie — 문자열 검색의 끝판왕
검색창에 'app'만 쳤는데 자동완성이 뜬다?
구글 검색창에 글자를 하나만 쳐도 수십 개의 추천어가 뜹니다. 수십억 개의 검색어 중에서 어떻게 실시간으로 후보를 찾을 수 있을까요?
해시맵으로는 'prefix 매칭'을 효율적으로 할 수 없다
Trie(트라이)는 문자열을 문자 단위로 저장하여 접두사 검색을 O(m) — 문자열 길이만큼 — 에 해결합니다.
핵심 개념
Trie
문자열을 문자 단위로 저장하는 트리 자료구조 (prefix tree)
Prefix Search
접두사로 시작하는 모든 문자열을 빠르게 찾는 연산
핵심 내용
해시맵은 정확한 키만 찾습니다. 'app'로 시작하는 모든 단어를 찾으려면?
Trie는 문자 하나하나를 노드로 저장합니다. 'apple', 'app', 'apt' → 'a'-'p' 경로를 공유합니다
Trie의 핵심: 공통 접두사를 공유하여 메모리를 절약하고, 접두사 검색이 O(m)에 가능
Trie의 각 노드는 두 가지만 가지고 있습니다
class TrieNode:
def __init__(self):
self.children = {} # char → TrieNode
self.is_end = False # 단어의 끝인지 표시children: 자식 노드 딕셔너리 (최대 26개 — 알파벳) is_end: True이면 루트→현재 경로가 완전한 단어
단어를 한 글자씩 따라가며 없는 노드는 새로 만듭니다
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True시간 복잡도: O(m) (m = 단어 길이) 공간: 최악 O(m) — 새 노드 m개 생성
search는 정확히 일치하는 단어, startsWith는 접두사 존재 여부를 확인합니다
def search(self, word: str) -> bool:
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end # 단어 끝이어야 True
def startsWith(self, prefix: str) -> bool:
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True # 경로만 존재하면 Truesearch('app'): 'a'→'p'→'p' 이동 후 is_end 확인 startsWith('app'): 'a'→'p'→'p' 경로 존재만 확인 둘 다 O(m) — m은 문자열 길이
'apple'과 'app'을 삽입한 뒤 search와 startsWith를 추적합니다
search는 is_end까지 확인, startsWith는 경로만 확인 — 이 차이가 핵심!
자동완성 = startsWith + DFS로 접두사 아래 모든 단어 수집
def autocomplete(self, prefix: str) -> list[str]:
node = self.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
# DFS로 prefix 아래 모든 단어 수집
results = []
def dfs(n, path):
if n.is_end:
results.append(prefix + path)
for c, child in n.children.items():
dfs(child, path + c)
dfs(node, '')
return resultsautocomplete('app') → ['app', 'apple', 'application', ...] prefix 이동 O(m) + DFS로 후보 수집
면접 포인트 • Trie vs 해시맵: prefix 검색이 필요하면 Trie • Trie vs 정렬+이진탐색: Trie가 동적 삽입에 유리 • 공간 최적화: 압축 Trie (Radix Tree)로 노드 수 감소
Trie에서 search('app')과 startsWith('app')의 차이는?
Trie에 'cat', 'car', 'card'를 넣었을 때 startsWith('ca')의 결과는?
Trie insert의 시간 복잡도에서 m이 의미하는 것은?
핵심 용어
Trie (트라이)
문자 단위로 저장하는 트리, prefix tree라고도 함
Prefix Search
접두사로 시작하는 모든 문자열을 빠르게 탐색
TrieNode
children 딕셔너리 + is_end 플래그로 구성
insert
O(m) — m은 단어 길이
search
O(m)
startsWith
O(m)
공간
O(N × m) — N개 단어, 평균 길이 m
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작