트라이 (Trie)

코드 예시

다음은 영어 소문자를 다루는 트라이의 삽입과 접두사 검색 자바(Java) 구현이다.

class Trie {
    static class Node {
        Node[] children = new Node[26];
        boolean isEnd;
    }
    Node root = new Node();

    void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) cur.children[i] = new Node();
            cur = cur.children[i];
        }
        cur.isEnd = true;
    }

    boolean startsWith(String prefix) {
        Node cur = root;
        for (char c : prefix.toCharArray()) {
            cur = cur.children[c - 'a'];
            if (cur == null) return false;
        }
        return true; // 완전 일치라면 cur.isEnd까지 확인한다
    }
}

활용 사례

가장 대표적인 활용은 자동 완성이다. 사용자가 입력한 접두사까지 경로를 따라 내려간 뒤 그 아래 부분 트리를 순회하면 해당 접두사로 시작하는 모든 후보를 얻는다. 검색어 추천, 사전 앱, IDE의 코드 완성이 이 원리다. 맞춤법 검사와 금칙어 필터링에도 쓰이며, 여러 패턴을 동시에 찾는 아호 코라식(Aho-Corasick) 알고리즘은 트라이에 실패 링크를 더한 확장이다. 문자 대신 비트를 간선으로 쓰는 이진 트라이는 XOR 최댓값 문제나 IP 주소의 최장 접두사 매칭(longest prefix matching)에 활용된다. 코딩 테스트에서는 "문자열 집합에서 접두사 관계 판정", "검색어 자동 완성 구현" 유형이 트라이 문제의 전형이다.

다른 구조와의 선택 기준

완전 일치 조회만 필요하면 구현이 간단하고 메모리 효율이 좋은 해시 테이블이 낫다. 접두사 질의, 사전순 순회, 공통 접두사 압축이 필요할 때 트라이가 정답이 된다. 데이터가 정적이고 메모리가 빠듯하면 정렬된 배열 위에서 이진 탐색으로 접두사 범위를 찾는 절충안도 실무에서는 유효하다. 결국 "접두사"라는 단어가 요구사항에 등장하는 순간 트라이를 떠올리는 것이 올바른 감각이다.

면접에서 이렇게 물어본다

• 트라이의 구조를 설명하고, 검색 시간이 저장된 단어 수와 무관한 이유를 말해 보라.
• 트라이와 해시 테이블의 장단점을 비교하고 트라이를 선택해야 하는 상황을 들어 보라.
• 노드에 단어 끝 표시가 필요한 이유를 예를 들어 설명해 보라.
• 자동 완성 기능을 트라이로 설계하는 과정을 설명해 보라.
• 트라이의 메모리 낭비 문제와 이를 완화하는 방법을 설명해 보라.