트라이 (Trie, 접두사 트리)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 4분 · 1,331자/단어 #algorithm #string #trie #tree #data-structure

정의

트라이 (Trie) 는 Edward Fredkin 이 1960년 제안한 문자열 집합을 저장하는 트리 자료구조. 각 노드는 문자 하나, 간선은 다음 문자로의 전이. 루트에서 한 노드까지의 경로가 하나의 문자열을 형성.

이름은 retrieval (검색) 에서 유래했지만 “try” 로 발음 (구별 위해).

공통 접두사를 공유하는 문자열들이 경로를 공유하므로, 접두사 검색 / autocomplete / 사전 저장에 효율적.

문제 상황과 동기

N 개의 문자열 집합 S, 각 길이 평균 M.

naive (배열 저장): 문자열 검색 O(N×M). 접두사 검색 (모든 문자열 비교) O(N×M).
Trie: 삽입 O(M), 검색 O(M), 접두사 매칭 O(M) + 결과 개수 O(K).

핵심 통찰: 공통 접두사는 한 번만 저장. “cat”, “car”, “card” 는 루트 → c → a 까지 경로 공유. ‘a’ 노드 아래 ‘t’, ‘r’ 두 분기.

자주 등장하는 위치: autocomplete (검색창 자동완성), 사전 구현, IP 라우팅 테이블 (longest prefix match), 스펠체커, 문자열 집합 membership 쿼리.

시각화

핵심 아이디어

구조:

각 노드는 자식 맵 (문자 → 다음 노드)과 단어 종료 플래그 (isEnd).
루트는 빈 문자열. 루트에서 한 노드까지의 경로 = 접두사.
isEnd = true 인 노드 = 한 단어의 끝.

삽입 (insert):

insert(word):
    node = root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = new TrieNode()
        node = node.children[ch]
    node.isEnd = true

검색 (search):

search(word):
    node = root
    for ch in word:
        if ch not in node.children:
            return false
        node = node.children[ch]
    return node.isEnd

접두사 검색 (startsWith):

startsWith(prefix):
    node = root
    for ch in prefix:
        if ch not in node.children:
            return false
        node = node.children[ch]
    return true  # prefix 경로 존재하면 true

invariant: 루트에서 임의 노드까지의 경로 = 어떤 문자열의 접두사. isEnd = true 노드 = 완전한 단어.

알고리즘

Trie 클래스 설계 (C++)

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

class Trie {
    TrieNode* root;
public:
    Trie() { root = new TrieNode(); }
    
    void insert(string word) { /* 위 pseudocode */ }
    bool search(string word) { /* 위 pseudocode */ }
    bool startsWith(string prefix) { /* 위 pseudocode */ }
};

autocomplete (접두사로 시작하는 모든 단어)

autocomplete(prefix):
    node = startsWith_node(prefix)  # prefix 까지 이동
    if not node: return []
    results = []
    dfs(node, prefix, results)
    return results

dfs(node, current_word, results):
    if node.isEnd:
        results.append(current_word)
    for ch, child in node.children:
        dfs(child, current_word + ch, results)

복잡도: O(M + K×L) (M = prefix 길이, K = 결과 개수, L = 평균 단어 길이).

구현

// Trie (접두사 트리) - 삽입, 검색, 접두사 검색 O(M)
#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
  unordered_map<char, TrieNode*> children;
  bool isEnd = false;
};

class Trie {
  TrieNode* root;
public:
  Trie() { root = new TrieNode(); }
  
  void insert(string word) {
      TrieNode* node = root;
      for (char ch : word) {
          if (!node->children[ch])
              node->children[ch] = new TrieNode();
          node = node->children[ch];
      }
      node->isEnd = true;
  }
  
  bool search(string word) {
      TrieNode* node = root;
      for (char ch : word) {
          if (!node->children[ch]) return false;
          node = node->children[ch];
      }
      return node->isEnd;
  }
  
  bool startsWith(string prefix) {
      TrieNode* node = root;
      for (char ch : prefix) {
          if (!node->children[ch]) return false;
          node = node->children[ch];
      }
      return true;
  }
};

int main() {
  Trie trie;
  trie.insert("cat");
  trie.insert("car");
  trie.insert("card");
  cout << trie.search("cat") << "\n";         // 1
  cout << trie.search("car") << "\n";         // 1
  cout << trie.search("ca") << "\n";          // 0 (접두사만 존재)
  cout << trie.startsWith("ca") << "\n";      // 1
  cout << trie.startsWith("dog") << "\n";     // 0
  return 0;
}

# Trie (접두사 트리) - 삽입, 검색, 접두사 검색 O(M)
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("card")
print(int(trie.search("cat")))         # 1
print(int(trie.search("car")))         # 1
print(int(trie.search("ca")))          # 0
print(int(trie.starts_with("ca")))     # 1
print(int(trie.starts_with("dog")))    # 0

// Trie (접두사 트리) - 삽입, 검색, 접두사 검색 O(M)
import java.util.*;
class TrieNode {
  Map<Character, TrieNode> children = new HashMap<>();
  boolean isEnd = false;
}

class Trie {
  TrieNode root = new TrieNode();
  
  void insert(String word) {
      TrieNode node = root;
      for (char ch : word.toCharArray()) {
          node.children.putIfAbsent(ch, new TrieNode());
          node = node.children.get(ch);
      }
      node.isEnd = true;
  }
  
  boolean search(String word) {
      TrieNode node = root;
      for (char ch : word.toCharArray()) {
          if (!node.children.containsKey(ch)) return false;
          node = node.children.get(ch);
      }
      return node.isEnd;
  }
  
  boolean startsWith(String prefix) {
      TrieNode node = root;
      for (char ch : prefix.toCharArray()) {
          if (!node.children.containsKey(ch)) return false;
          node = node.children.get(ch);
      }
      return true;
  }
}

public class Main {
  public static void main(String[] args) {
      Trie trie = new Trie();
      trie.insert("cat");
      trie.insert("car");
      trie.insert("card");
      System.out.println(trie.search("cat") ? 1 : 0);         // 1
      System.out.println(trie.search("car") ? 1 : 0);         // 1
      System.out.println(trie.search("ca") ? 1 : 0);          // 0
      System.out.println(trie.startsWith("ca") ? 1 : 0);      // 1
      System.out.println(trie.startsWith("dog") ? 1 : 0);     // 0
  }
}

결과

복잡도

연산	시간	공간
삽입 (insert)	O(M)	O(M) (새 노드 최대 M 개)
검색 (search)	O(M)	-
접두사 검색 (startsWith)	O(M)	-
autocomplete	O(M + K×L)	-
전체 공간	O(N×M×Σ) worst	Σ = 알파벳 크기

공간 최적화:

children 을 unordered_map 대신 배열 (소문자만: TrieNode* children[26]) → O(1) 접근, 공간 O(26×노드 수).
압축 Trie (radix tree): 단일 자식 노드를 압축. “cat”, “category” → “cat” 노드 하나에 “egory” 간선.

변형 / 활용

1. XOR 최대화 (비트 Trie)

정수 배열에서 한 원소와 XOR 최대값. 각 정수를 이진 비트로 Trie 에 삽입. MSB 부터 반대 비트 선택 → O(log MAX).

BOJ 13537 (Persistent Segtree) 계열 문제 참고

2. 사전 순서 k 번째 문자열

Trie 에 각 노드마다 서브트리 단어 개수 저장. DFS + rank 쿼리 O(M).

3. Aho-Corasick

Trie + failure link (KMP 의 failure function). 다중 패턴 일괄 검색 O(N + M + 출현 수).

4. 접미사 Trie (Suffix Trie)

문자열의 모든 접미사를 Trie 에 삽입. 공간 O(N²) → Suffix Array 또는 Suffix Tree 로 최적화.

함정

1. 메모리 폭발

알파벳 크기 Σ = 26 일 때, 노드당 26 포인터. N=10^6 단어, 평균 길이 10 → 최악 10^7 노드 × 26 = 2.6억 포인터 (몇 GB).

해결: unordered_map (실제 자식만 저장) 또는 압축 Trie.

2. isEnd 플래그 누락

“cat”, “category” 삽입 후 search("cat") 가 false 이면 isEnd 설정 빠뜨림.

3. 삭제 구현 복잡

노드를 삭제하려면 부모 포인터 역추적 또는 재귀 필요. 자식이 없는 노드만 삭제해야 다른 단어 영향 없음.

4. 대소문자 / 특수문자

입력이 대소문자 섞이거나 공백 / 특수문자 포함 시 통일 필요. 보통 소문자로 정규화.

5. 접두사와 완전 매칭 혼동

startsWith("ca") = true 지만 search("ca") = false (단어 아님).

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 5052	전화번호 목록	31.8%	kokoa-lab
BOJ 14425	문자열 집합	45.2%	kokoa-lab
BOJ 14426	접두사 찾기	41.3%	kokoa-lab
BOJ 16906	새로운 전화번호	18.7%	kokoa-lab

참고

이 글의 용어 (4개)

문자열 (String)algorithm: 정의 문자열 (String) 은 문자(character)의 순서 있는 나열. 프로그래밍에서는 연속된 메모리에 저장된 문자 배열 로 구현되며, 각 문자는 ASCII(7비트) 또는 …
Aho-Corasick (아호-코라식)algorithm: 정의 Aho-Corasick 은 Alfred Aho 와 Margaret Corasick 이 1975년 고안한 다중 패턴 문자열 매칭 알고리즘. Trie 에 KMP failure …
KMP 문자열 매칭 (Knuth-Morris-Pratt)algorithm: 정의 KMP (Knuth-Morris-Pratt) 는 Donald Knuth, James H. Morris, Vaughan Pratt 가 1977년 고안한 선형 시간 문자열 매칭…
Suffix Array (접미사 배열)algorithm: 정의 Suffix Array (SA, 접미사 배열) 는 문자열 s 의 모든 접미사를 사전순 정렬한 인덱스 배열. SA[i] = 시작 위치 (0-indexed). 보통 LCP (L…