[100일의 IT 초보 탈출] #68 Trie _ 자동완성과 검색어 추천의 핵심

오늘은 무엇을 배우게 될까요?

 

검색창에 “co”를 입력하면 “coffee”, “code”, “cookie” 같은 단어들이

자동으로 추천되는 걸 본 적 있으시죠?

 

이런 기능은 단순 반복문이 아닌

특별한 자료구조를 사용해 동작합니다.

그 구조가 바로 오늘 배울 Trie(트라이)입니다.

 

---

 

Trie란 무엇인가요?

 

Trie는 문자열을 트리 형태로 저장하는 자료구조입니다.

보통 알파벳 단어의 사전(dictionary)이나 자동완성 기능에 사용됩니다.

 

• 각 노드는 하나의 문자(character)를 나타냅니다.
• 루트부터 한 글자씩 따라 내려가면 하나의 단어가 완성됩니다.

 

---

 

 

예시 구조 (단어 삽입 예시)

 

단어 목록: ["cat", "car", "dog", "dot"]

(root)
 ├─ c
 │   └─ a
 │       ├─ t (끝)
 │       └─ r (끝)
 └─ d
     ├─ o
         ├─ g (끝)
         └─ t (끝)

 

---

핵심 기능

 

1. 삽입 (Insert): 문자열을 트리에 추가
2. 탐색 (Search): 문자열이 존재하는지 확인
3. 접두사 검색 (StartsWith): 특정 접두사로 시작하는 단어가 있는지 확인

 

---

Python 코드 구현

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        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
    
    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end
    
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

 

---

사용 예시

trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("dog")

print(trie.search("car"))       # True
print(trie.search("can"))       # False
print(trie.starts_with("ca"))   # True
print(trie.starts_with("do"))   # True
print(trie.starts_with("da"))   # False

 

---

시간 복잡도

 

삽입	O(L)
탐색	O(L)
접두사 검색	O(L)

L = 단어 또는 접두사의 길이

 

→ 입력한 길이만큼만 탐색하면 되므로 매우 빠릅니다.

 

---

활용 분야

 

자동완성	입력한 접두사로 시작하는 단어 추천
검색 추천	사용자가 자주 검색하는 단어 제안
사전 앱	단어 존재 여부 빠르게 확인
게임	단어 만들기 게임에서 유효성 검사
데이터 압축	공통 접두사 기반의 효율적인 저장

 

---

Trie vs 일반 리스트 검색

 

리스트 선형 탐색	단어 하나하나 순회	O(NL)
Trie	트리 탐색만으로 가능	O(L)

(N: 전체 단어 수, L: 단어 길이)

 

---

 

 

한 줄 요약

 

👉 Trie는 접두사 기반 문자열 검색과 자동완성 시스템을 구현할 때 필수적인 자료구조입니다.

빠르고, 중복이 적고, 문자열 중심의 문제를 깔끔하게 해결합니다.