트라이

어떤 문제를 푸는가

문자열의 집합을 글자 단위로 가지를 뻗는 트리 에 저장해, "이 문자열이
집합에 있는가", "이 접두사로 시작하는 단어가 있는가" 같은 질의를 문자열
길이에 비례하는 시간 에 답합니다. 자동 완성, 사전, 접두사 카운팅의 토대입니다.

구조 — 글자를 따라 내려가는 길

루트에서 시작해 한 글자씩 자식으로 내려가며 문자열을 따라갑니다. 공통 접두사를
가진 단어들은 트리의 앞부분 경로를 공유 합니다.

"cat", "car", "card", "dog" 를 담은 트라이

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

각 노드는 자식 포인터들(보통 알파벳 개수만큼의 배열 또는 맵)과 "여기서 단어가
끝나는가"를 나타내는 표시를 가집니다. card는 car의 경로를 그대로 지나
d로 한 칸 더 갑니다.

핵심 연산

\(L\)은 문자열 길이. 삽입·탐색 비용이 트리에 담긴 단어 수와 무관 하다는 점이
해시/정렬과 다른 강점입니다.

해시·정렬과의 비교

• 해시 집합 — 평균 \(O(L)\)로 존재 판정은 빠르지만, "접두사로 시작하는
  단어가 있나" 같은 질의는 어렵습니다.
• 정렬 + 이분 탐색 — 접두사 질의는 가능하나 동적 삽입이 불편합니다.
• 트라이 — 접두사 관련 질의에 자연스럽고, 동적 삽입/삭제도 쉽습니다.

복잡도와 공간

• 시간: 각 연산 \(O(L)\).
• 공간: 노드 수 × 알파벳 크기. 자식을 배열 로 두면 빠르지만 메모리가 크고,
  맵/해시 로 두면 메모리는 절약되나 상수가 큽니다.

전체 문자열 길이 합이 \(S\)면 노드 수는 \(O(S)\) 이하입니다(공통 접두사는 공유).
다음 강의에서 구현과 응용을 봅니다.

배열 기반 트라이 (C++, 소문자)

자식을 26칸 배열로 두는 가장 빠른 형태입니다.

#include <bits/stdc++.h>
using namespace std;

struct Trie {
    struct Node {
        int child[26];
        bool end = false;
        int cnt = 0;            // 이 노드를 지나는 단어 수(접두사 카운트용)
        Node() { fill(child, child + 26, -1); }
    };
    vector<Node> t;
    Trie() { t.emplace_back(); }   // 루트 = 인덱스 0

    void insert(const string& s) {
        int cur = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[cur].child[c] == -1) {
                t[cur].child[c] = t.size();
                t.emplace_back();
            }
            cur = t[cur].child[c];
            t[cur].cnt++;
        }
        t[cur].end = true;
    }

    bool search(const string& s) {     // 정확한 단어 존재
        int cur = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[cur].child[c] == -1) return false;
            cur = t[cur].child[c];
        }
        return t[cur].end;
    }

    int countPrefix(const string& p) { // p로 시작하는 단어 수
        int cur = 0;
        for (char ch : p) {
            int c = ch - 'a';
            if (t[cur].child[c] == -1) return 0;
            cur = t[cur].child[c];
        }
        return t[cur].cnt;
    }
};

vector<Node>에 노드를 풀어 담고 인덱스로 가리키면 포인터 관리가 단순하고
캐시 친화적입니다.

파이썬 구현 (딕셔너리 기반)

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, s):
        node = self.root
        for ch in s:
            node = node.setdefault(ch, {})
        node['$'] = True              # 단어 끝 표시

    def search(self, s):
        node = self.root
        for ch in s:
            if ch not in node:
                return False
            node = node[ch]
        return '$' in node

딕셔너리 기반은 알파벳이 크거나 유니코드일 때 편하지만 상수가 큽니다.

흔한 함정

• 종료 표시 누락 — end/'$'가 없으면 "car"가 사전에 있는지와 "car가
  단지 다른 단어의 접두사인지"를 구분 못 합니다.
• 메모리 폭발 — 배열형은 노드당 26(또는 알파벳 크기) 칸. 노드가 많으면
  메모리 초과. 맵형이나 압축 트라이를 고려.
• 알파벳 범위 — 대소문자·숫자·특수문자가 섞이면 인덱싱 범위를 맞추기.
• 삭제 — 카운트(cnt)를 두면 단어 삭제 시 경로의 카운트를 줄여 관리.

응용 패턴

• 사전 / 자동 완성 — 접두사로 내려간 뒤 그 아래 단어들을 수집.
• 접두사로 시작하는 단어 수 — cnt 필드.
• XOR 최대/최소 (비트 트라이) — 정수를 이진 비트열로 보고 트라이에 넣어,
  각 비트에서 반대 비트로 내려가면 XOR 최대를 \(O(\text{비트 수})\)에.
• 여러 패턴 동시 검색 — 트라이에 실패 링크를 더한 아호-코라식(상위 단원).
• 문자열 집합의 공통 접두사 — 분기가 생기는 지점까지 내려가기.

트라이는 "공통 접두사를 공유한다"는 단순한 구조에서 출발하지만, 비트 트라이와
아호-코라식 같은 강력한 확장의 출발점이라는 점에서 폭넓게 쓰입니다.

출제 신호

• "문자열 집합에서 접두사로 검색/개수/존재 판정" — "전화번호가 다른
  번호의 접두사인가"(일관성), "자동완성", "사전에서 시작하는 단어 수"
• "여러 문자열을 글자 단위로 공유하며 저장해야 할 때" — 같은 접두사가
  많은 대량 단어 입력
• "수들의 XOR 최대 쌍" — 비트(0/1) 트라이라는 강력한 변장 출제
• 제약 신호: 문자열 총 길이 합 \(\le 10^6\) 급. 트라이의 시간·공간은
  개별 길이가 아니라 총 길이 합에 비례한다는 감각이 중요합니다.

해시 셋으로 "완전 일치"는 되지만 접두사 질의는 안 된다는 것, 정렬 +
이분 탐색으로도 접두사 검색이 가능하지만 삽입이 섞이면 트라이가 자연스럽다는
것 — 이 비교가 선택 기준입니다.

풀이 결정 절차

1. 알파벳 크기를 확정합니다 — 소문자 26, 숫자 10, 비트 2. 이것이 노드의
   분기 수입니다.
2. 노드에 어떤 정보가 필요한지 정합니다 — end(단어 끝 표시)만으로 되는지,
   cnt(이 노드를 지나는 단어 수)가 필요한지. "접두사로 가지는 단어 수"
   질의는 cnt, "정확히 이 단어 존재" 질의는 end입니다. 둘을 혼동하면 오답.
3. 메모리를 추산합니다 — 노드 수 \(\le\) 총 길이 합. 자식을 고정 배열로 들면
   노드당 26포인터, \(10^6\) 노드면 1억 항목으로 터집니다. 알파벳이 크고
   단어가 길면 dict/unordered_map 자식이나 2차원 정수 배열 + 노드 풀이
   안전합니다.

자주 하는 실수

• 포인터 노드 남발로 메모리 초과 / 느린 할당 — C++에서 new를 글자마다
  부르는 대신, 정적 배열 풀에 인덱스로 노드를 만드는 방식이 빠르고 안전합니다.

int nxt[MAXN][26], cnt[MAXN], end_[MAXN], sz = 1;   // 0 번이 루트

void insert(const string& s) {
    int cur = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (!nxt[cur][c]) nxt[cur][c] = sz++;       // 노드 풀에서 할당
        cur = nxt[cur][c];
        cnt[cur]++;                                  // 지나는 단어 수
    }
    end_[cur]++;                                     // 끝나는 단어 수
}

• end와 cnt 혼동 — "she가 사전에 있는가"는 end_, "she로 시작하는
  단어가 몇 개인가"는 cnt. 전화번호 일관성 문제는 "삽입 중에 end를
  만나거나, 끝났는데 자식이 있으면" 모순 — 두 정보를 다 씁니다.
• 테스트케이스 간 초기화 — 노드 풀 방식은 sz = 1로 되돌리고 사용한
  노드만 지워야 합니다. memset 전체 초기화를 케이스마다 하면 그것만으로
  시간 초과가 나는 문제도 있습니다.
• XOR 트라이에서 비트 순서 — 반드시 최상위 비트부터 삽입/질의해야
  "가능한 한 다른 비트"를 고르는 탐욕이 성립합니다. 하위 비트부터 넣으면
  무의미합니다. 질의는 각 비트에서 반대 비트 자식이 있으면 그쪽, 없으면
  같은 쪽으로 내려갑니다.
• 파이썬 메모리 — 노드를 클래스로 만들면 무겁습니다. dict 중첩
  (trie = {}, 자식 = node.setdefault(ch, {}))이 간결하고 충분히 빠른
  경우가 많습니다.

연습 방법

사이드바 연습 목록의 접두사 일관성(전화번호) 문제로 end/cnt 설계를 익히고,
접두사 개수 질의 → 자동완성 비용류 → XOR 최대 쌍(비트 트라이) 순서로
확장하세요. 풀기 전에 "노드 수 상한 = 총 길이 합"과 "노드당 메모리"를
곱해 보는 습관이 메모리 초과를 미리 막아 줍니다. 태그된 문제 3문제 이상
해결 시 마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.