핵심 정리
| 연산 | 비용 | 기준 |
|---|---|---|
| insert | O(L) | 문자열 길이 L |
| search word | O(L) | 끝 표시까지 확인 |
| search prefix | O(L) | prefix 경로만 확인 |
| enumerate | O(하위 노드 수) | prefix 아래 단어 나열 |
csharp
sealed class TrieNode
{
public Dictionary<char, TrieNode> Next { get; } = new();
public bool IsWord { get; set; }
}구조
Trie는 문자열 전체를 하나의 키로 저장하지 않고, 각 문자를 노드 간 경로로 저장합니다. 같은 prefix를 가진 단어들은 앞쪽 노드를 공유합니다.
text
cat
car
care
c
└─ a
├─ t*
└─ r*
└─ e**는 단어가 끝나는 위치입니다. prefix 경로가 존재한다고 해서 그 prefix 자체가 단어라는 뜻은 아닙니다. 예를 들어 car가 단어인지 여부는 r 노드의 IsWord로 판단합니다.
삽입과 조회
삽입은 문자를 하나씩 따라가며 없는 노드를 만들고, 마지막 노드에 단어 종료 표시를 남깁니다.
csharp
void Insert(TrieNode root, string word)
{
TrieNode node = root;
foreach (char ch in word)
{
if (!node.Next.TryGetValue(ch, out TrieNode? next))
{
next = new TrieNode();
node.Next[ch] = next;
}
node = next;
}
node.IsWord = true;
}조회는 같은 경로를 따라가되, 단어 검색이면 마지막에 IsWord가 true인지 확인하고, prefix 검색이면 경로 존재만 확인합니다.
선택 기준
| 상황 | 선택 |
|---|---|
| prefix로 시작하는 단어를 자주 찾음 | Trie |
| 전체 문자열 존재 여부만 확인 | HashSet<string> |
| 정렬된 문자열 목록에서 prefix 범위 탐색 | 정렬 + binary search |
| 알파벳 범위가 작고 성능이 중요 | 배열 children |
| 문자 종류가 넓거나 sparse함 | Dictionary<char, TrieNode> |
Trie의 시간 복잡도는 단어 개수보다 문자열 길이에 직접 묶입니다. 단어가 많아도 prefix 길이만큼만 내려가면 후보 영역에 도달할 수 있습니다.
주의할 점
Trie는 노드를 많이 만들기 때문에 메모리를 많이 쓸 수 있습니다. 단어 수가 적거나 단순 존재 검사만 필요하면 HashSet<string>이 더 단순하고 빠를 수 있습니다.
또 Unicode 문자열을 문자 하나씩 처리할 때 char가 사용자가 보는 글자 하나와 항상 같지는 않습니다. 한글, emoji, 조합 문자가 중요한 입력에서는 문자열 분해 기준을 먼저 정하세요.