상품 검색창에 자동완성(autocomplete)을 붙인다. 사용자가 글자를 하나 칠 때마다 지금까지 친 글자로 시작하는 상품명을 보여 줘야 한다. 가장 먼저 떠오르는 코드는 한 줄이다.
const suggestions = names.filter(name => name.startsWith(query))상품명이 N개면 글자를 칠 때마다 N개를 모두 훑는다. 상품명마다 앞의 몇 글자를 비교하니 한 번에 O(N × L)(L은 입력한 글자 수)이고, 사용자가 다섯 글자를 치면 이 일을 다섯 번 한다. 입력은 앞 글자가 같은 채로 한 글자씩 늘어나는데, 매번 처음부터 다시 훑는 셈이다. 입력한 글자 수만큼만 걸어서 후보가 모인 곳에 바로 닿을 수는 없을까?
이 장의 구조는 트라이(trie)다. 접두어 (prefix tree)라고도 부른다. 단어를 글자 단위로 쪼개 나무에 걸어 두고, 앞부분이 같은 단어끼리 같은 가지를 함께 쓴다.
트라이: 글자 하나가 한 걸음
트라이의 노드는 두 가지만 가진다. 다음 글자 → 자식 노드로 가는 맵(kids)과, 루트에서 여기까지 걸어온 글자들이 사전에 넣은 단어인지 나타내는 표시(end)다. 단어를 넣을 때는 루트에서 출발해 글자마다 그 글자의 자식으로 한 칸 내려간다. 자식이 없으면 새로 만든다. 마지막 글자에 닿으면 end를 켠다.
type TrieNode = { kids: Map<string, TrieNode>; end: boolean }const make = (): TrieNode => ({ kids: new Map(), end: false }) function insert(root: TrieNode, word: string) { let node = root for (const ch of word) { if (!node.kids.has(ch)) node.kids.set(ch, make()) node = node.kids.get(ch)! } node.end = true}
빈 트라이에 car, cat, cart를 차례로 넣는다. 루트를 빼고 노드는 모두 몇 개 생길까?
선택지와 해설 보기
실험 트라이에 단어 넣기
단어를 눌러 차례로 넣어 보세요. 노드 한 줄이 글자 하나, 들여쓰기가 깊이, ●가 단어 끝 표시입니다. 방금 만든 노드는 파랑에 '새 노드'로 표시합니다.
- 해볼 것
- 빈 트라이에 car, cat, cart를 넣고 노드 수를 글자 수와 견줘 본다
- 비우고 to, tea, ten, in을 넣어 본다
car, cat, cart는 글자가 모두 10개지만 노드는 5개다. cat을 넣을 때는 c와 a가 이미 있어서 t 하나만 만들었고, cart는 c, a, r을 지나 t 하나만 만들었다. 앞부분이 같은 단어가 많을수록 노드가 덜 생긴다. 단어 하나를 넣는 비용은 단어 길이 L만큼 걷는 O(L)이고, 트라이에 단어가 몇 개 들어 있든 같다.
end 표시가 따로 필요한 이유도 보인다. car는 cart의 앞부분이기도 하다. r 노드에 end가 켜져 있어야 "car도 단어다"를 알 수 있다.
접두어로 찾기: 입력 길이만큼만 걷는다
자동완성은 두 단계다. 먼저 루트에서 접두어 글자를 따라 접두어 노드까지 걷는다. 그다음 그 노드 아래를 모두 훑으며 end가 켜진 노드의 경로를 모은다.
function suggest(root: TrieNode, prefix: string): string[] { let node = root for (const ch of prefix) { const next = node.kids.get(ch) if (!next) return [] node = next } const out: string[] = [] const walk = (n: TrieNode, path: string) => { if (n.end) out.push(path) for (const [ch, kid] of n.kids) walk(kid, path + ch) } walk(node, prefix) return out}
실험 접두어로 시작하는 단어 모으기
사전에 car, cart, cat, dog, door를 넣어 두었습니다. 접두어 글자를 따라 걸어간 길은 파랑, 그 아래 훑은 노드는 노랑, 찾은 단어는 초록이고, 보지 않은 노드는 흐리게 둡니다. 'c'나 'do'를 고르면 훑기만 하고 단어는 아닌 노드(노랑)가 보입니다.
- 해볼 것
- 접두어 'do'로 바꿔 c 가지는 보지 않고 그 아래만 훑는 것을 본다
- 'cb'처럼 없는 접두어로 걸음이 어디서 멈추는지 본다
접두어 ca는 두 걸음 만에 접두어 노드에 닿는다. 그 아래에 있는 car, cart, cat만 훑고, dog·door 가지는 보지도 않는다. 걷는 비용은 접두어 길이 L에 비례하는 O(L)이고, 모으는 비용은 접두어 노드 아래의 노드 수에 비례한다. 둘 다 사전 전체 단어 수 N과 상관이 없다. 접두어로 시작하는 단어가 없으면 걷는 도중 자식이 없어 바로 끝난다(cb는 c로 한 걸음 내려간 뒤 b 자식이 없어 멈춘다).
결과 순서는 자식 맵을 도는 순서를 따른다. JavaScript Map은 넣은 순서대로 순회하고(MDN: Map), Python dict도 3.7부터 넣은 순서를 지킨다(Python 문서: dict). 그래서 두 언어의 출력이 같다. 가나다순이 필요하면 모은 뒤 정렬하거나, 자식을 글자 순으로 돌면 된다.
실제 자동완성은 모든 후보가 아니라 상위 몇 개만 보여 준다. 접두어 노드 아래 단어가 수만 개일 수 있으니, 모으는 단계에서 개수를 세다 멈추거나 노드마다 "이 아래 인기 단어 상위 k개"를 미리 적어 두는 식으로 모으는 비용을 줄인다.
정렬된 배열과 견주기
트라이만 답은 아니다. 상품명을 정렬해 두면 같은 접두어로 시작하는 이름은 한 덩어리로 붙어 있다. 이분 탐색(binary search)으로 "접두어보다 작지 않은 첫 이름"의 위치를 찾고, 거기서부터 접두어로 시작하는 동안만 읽으면 된다(이분 탐색 노트). 이분 탐색은 비교를 log₂ N번쯤(6장의 후보를 절반씩 버리는 횟수. 『개발 수학』 Unit 2) 하고 비교마다 최대 L글자를 보니 O(L × log N), 그 뒤 결과 k개를 읽는다.
| 트라이 | 정렬 배열 + 이분 탐색 | |
|---|---|---|
| 접두어 노드·위치 찾기 | O(L) | O(L × log N) |
| 단어 하나 넣기 | O(L) | 자리를 찾고 뒤를 한 칸씩 밀어 O(N) |
| 메모리 | 글자마다 노드 하나와 자식 맵 하나 | 문자열 배열 하나 |
| 구현 | 직접 짠다 | 표준 정렬 + 이분 탐색 몇 줄 |
log N은 N이 100만이어도 약 20이다. 목록이 거의 바뀌지 않고 접두어 검색만 한다면 정렬 배열로 충분한 경우가 많고, 메모리도 훨씬 적게 든다. 트라이 노드는 글자 하나마다 객체와 맵을 하나씩 만들기 때문이다. 트라이가 앞서는 때는 단어를 자주 넣고 빼거나, 글자를 하나씩 받으며 걸어가는 일(입력에 맞춰 한 칸씩 내려가기, 다음 절의 금칙어 검사)이 필요할 때다. 어느 쪽이 빠른지는 데이터 크기와 모양에 달려 있으니 실제 데이터로 재 보고 고른다.
실무에서 만나는 트라이
라우터 경로 매칭. /users/:id/posts 같은 경로를 /로 나누면 세그먼트 목록이 된다. 세그먼트 하나를 글자 하나처럼 다루면 등록한 경로들이 트라이가 되고, 요청 경로를 세그먼트마다 한 칸씩 내려가며 맞는 핸들러를 찾는다. Fastify와 Restify가 쓰는 라우터 find-my-way는 README에서 내부적으로 래딕스 트리(radix tree, "compact Prefix Tree")를 쓴다고 밝힌다(find-my-way README). 래딕스 트리는 자식이 하나뿐인 노드가 줄줄이 이어진 구간을 간선 하나로 합친 트라이다. /users/처럼 갈라지지 않는 구간을 한 번에 비교해서 노드 수를 줄인다.
금칙어 필터. 금칙어를 모두 트라이에 넣어 두면, 글 본문의 위치마다 트라이를 따라 걸어 보며 end에 닿는지 본다. 금칙어마다 본문 전체를 includes로 훑는 대신 위치마다 한 번만 걷는다. 장 끝 보너스 문제가 같은 걸음을 쓴다.
검색 엔진의 색인. 문서 본문에서 "이 단어가 들어 있는 문서"를 찾는 일은 트라이가 아니라 단어 → 문서 목록 맵인 역색인(inverted index)으로 푼다(역색인 노트). 트라이는 그 앞에서 "사용자가 치는 중인 단어"를 완성해 주는 쪽에 어울린다.
실무 코드에서 찾아보기
트라이 코드는 짧아서 한두 글자만 틀려도 결과가 그럴듯하게 틀린다. 단어 끝 표시를 어느 노드에 붙이는지, 모은 경로가 어디서 시작하는지 보자.
함정 찾기 AI가 짠 자동완성 트라이, 어디가 틀렸을까?
“단어를 넣는 insert, 단어가 사전에 있는지 보는 has, 접두어로 시작하는 단어를 모두 돌려주는 suggest를 트라이로 짜 줘.”
의심스러운 줄을 모두 눌러 표시한 뒤 “검토 끝”을 누르세요. 함정은 3개입니다.
정리하면 세 줄이 틀렸다. 끝 표시를 루트에 붙여서 접두어가 한 글자라도 있으면 suggest는 늘 빈 배열을 돌려주고, 닿기만 하면 참인 has는 cart만 넣어도 car를 단어로 판정하며, 빈 경로로 모으면 ca의 결과가 car 대신 r로 나온다.
확인 문제 장을 덮기 전에 떠올려 보기
1. 단어 N개가 든 트라이에서 길이 L인 접두어의 노드를 찾는 비용은?
2. 트라이 노드에 단어 끝 표시(end)가 따로 필요한 이유는?
3. 목록이 거의 바뀌지 않고 접두어 검색만 할 때, 정렬 배열 + 이분 탐색이 트라이보다 나은 점은?
더 풀어 보기(선택) · 띄어쓰기 없는 검색어 나누기
검색창에 applepie처럼 띄어 쓰지 않은 검색어가 들어왔다. 사전 단어 목록이 주어질 때, 이 문자열을 사전 단어만 이어 붙여 만들 수 있는지(단어는 여러 번 써도 된다) 판정해 보자. 각 시작 위치에서 사전 단어를 하나씩 startsWith로 견주지 말고, 트라이로 한 번에 걸어 보자.
사전 [app, apple, pie, le], applepie → 나눌 수 있다 (apple + pie, app + le + pie) 사전 [cat, cats, sand, do], catsdog → 나눌 수 없다