우리가 구글이나 네이버 검색창에 '코딩'이라는 두 글자만 입력하더라도 하단에 '코딩 테스트', '코딩 학원', '코딩 기초' 등 수많은 연관 검색어가 0.1초도 안 되어 쏟아져 나옵니다. 데이터베이스에 저장된 수억 개의 검색어 데이터 속에서 어떻게 이렇게 찰나의 순간에 특정 문자로 시작하는 단어들만 쏙쏙 뽑아올 수 있는 것일까요? 만약 단순한 배열이나 해시 테이블(Hash Table)을 사용했다면 이렇게 부분 일치(Prefix) 기반의 자동완성 기능을 구현하는 것은 불가능에 가깝습니다. 오직 문자열의, 문자열에 의한, 문자열을 위한 고속 탐색 전용 자료구조인 트라이(Trie)가 존재하기에 가능한 일입니다. 코딩 테스트 문자열 파트의 최종 보스격인 트라이의 동작 원리와 메모리 트레이드오프(Trade-off)를 완벽하게 정복해 봅니다.
1. 트라이(Trie)란 무엇인가? (접두사 트리)
트라이(Trie)는 검색(Retrieval)이라는 단어의 중간 철자에서 이름을 따온 트리 자료구조의 일종입니다. 텍스트 자동 완성이나 사전 찾기 기능에 압도적인 퍼포먼스를 내기 때문에 접두사 트리(Prefix Tree)라고도 불립니다.
일반적인 트리가 노드에 전체 데이터를 담는다면, 트라이는 문자열을 글자 단위로 갈기갈기 찢어서 노드에 하나씩 저장하고 부모-자식 관계로 엮어버린다는 매우 독창적인 구조를 가집니다.
2. 트라이의 동작 원리와 구조 분석
가상의 트라이 구조에 "CAT", "CAR", "DOG"라는 세 단어를 저장한다고 시뮬레이션해 봅시다.
2-1. 단어 삽입(Insert) 과정
- 루트(Root) 노드는 항상 비어있는 상태로 둡니다.
- "CAT" 삽입: 루트 아래에 'C' 노드를 만듭니다. 'C' 아래에 'A' 노드를 만듭니다. 'A' 아래에 'T' 노드를 만듭니다. 그리고 마지막 'T' 노드에 "여기서 단어가 끝납니다(IsEnd = True)"라는 마킹을 해둡니다.
- "CAR" 삽입: 루트 아래에 'C'를 찾습니다. 아까 만들었으니 넘어갑니다. 'C' 아래 'A'도 넘어갑니다. 'A' 아래에 'R'은 없으므로 새롭게 'R' 노드를 만들고 자식으로 편입시킵니다. 그리고 끝남 마킹을 합니다.
- "DOG" 삽입: 루트 아래에 'D'가 없으니 'D' -> 'O' -> 'G'를 순서대로 새로 만듭니다.
이 과정을 거치면 "CA"라는 공통 접두사(Prefix)를 가진 "CAT"과 "CAR"는 'C'와 'A' 노드를 서로 공유하게 됩니다. 이것이 메모리를 절약하고 검색을 빠르게 만드는 핵심 비결입니다.
2-2. 압도적인 검색(Search) 속도의 마법
어떤 단어를 찾고자 할 때, 전체 데이터의 개수가 $N$개인 것은 전혀 중요하지 않습니다. 오직 "내가 찾고자 하는 문자열의 길이($L$)"만이 속도를 결정합니다. "CAR"를 검색한다면, 루트에서 'C' -> 'A' -> 'R'을 따라 노드를 세 번만 밟고 내려가면 끝입니다. 시간 복잡도는 O(L)로, 사실상 O(1)에 버금가는 상수 시간 탐색이나 다름없습니다. 해시 테이블이 '전체 일치'만 찾을 수 있는 반면, 트라이는 "CA"까지만 입력해도 해당 노드 아래에 매달린 모든 자식 노드들을 긁어모아 '자동완성' 기능을 뚝딱 만들어 낼 수 있습니다.
3. 트라이의 치명적인 한계: 최악의 공간 복잡도
이렇게 완벽해 보이는 트라이도 코딩 테스트 현장에서 함부로 남발해서는 안 되는 치명적인 이유가 있습니다. 바로 '메모리 잡아먹는 하마'라는 점입니다.
각 노드는 다음 글자로 연결될 수 있는 모든 가능성을 포인터 배열로 가지고 있어야 합니다. 영어 알파벳 소문자만 다룬다 해도, 노드 한 개당 무려 26칸짜리 배열을 메모리에 할당해야 합니다. 만약 저장하려는 단어들이 겹치는 철자가 하나도 없는 최악의 경우라면, 필요한 노드의 수는 (모든 단어의 길이 합) $\times 26$만큼 폭발적으로 증가하여 메모리 한도 초과(Memory Limit Exceeded)를 유발하게 됩니다. 이를 해결하기 위해 메모리를 압축하는 트라이나 `Map` 자료구조를 결합하는 최적화 기법을 사용하기도 합니다.
1. 트라이(Trie)는 문자열을 알파벳 단위로 쪼개어 트리 구조로 저장하는 접두사(Prefix) 탐색 최적화 자료구조입니다.
2. 데이터의 총량과 무관하게, 찾고자 하는 문자열의 길이(L)만큼만 탐색하면 되는 O(L)의 경이로운 검색 속도를 보여줍니다.
3. 구글의 검색어 자동완성, 철자 검사기 등에 필수적으로 사용되지만, 자식 노드를 위한 포인터 배열로 인해 막대한 메모리 공간을 소모한다는 단점이 있습니다.