트라이(Trie) 자료구조

---

목차

1. 트라이(Trie)란?

2. 트라이(Trie) 이해하기

3. 트라이(Trie)의 단점

4. 트라이(Trie) 접목하기

5. 트라이(Trie) 문제 풀어보기

---

트라이(Trie)란?

문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합을 표현하는 트리 자료구조이며,

우리가 원하는 원소를 찾는 작업을 O(n)에 해결 할 수 있는 자료구조이다.

이제 트라이에 대해 이해해보는 시간을 가져 보자.

그리고 다음 질문에 대해 한번 생각해보자.

map을 이용하면 충분히 트라이와 같은 효과를 낼 수 있지 않을까??

트라이(Trie) 이해하기

이번에는 그림을 통해 트라이를 이해해보고자 한다.

우선 문자열 5개 {"blog", "he", "her", "crocus", "cross"}를 가지고 있다고 생각해보자.

트라이는 이때 위와 같이 그림을 형성하게 된다.

사실상 트라이는 그림으로 보면 바로 이해가 되리라 생각이 든다.

루트 노드가 되는 가장 최상위 노드에는 어떠한 단어도 들어가지 않고,

루트 아래 노드부터 문자열들의 접두사가 하나씩 나타나게 된다.

예를들어보자. 

crocus는 c -> cr -> cro -> croc -> crocu -> crocus로 이루어지는데

이 과정에서 나타난 것들은 모두 crocus의 접두사이다.

다른 예제를 보자.

her은 h -> he -> her이 되고, her의 접두사에는 h, he가 존재한다.

이때 he는 문자열에서 나타난 종류 중 하나이다. 

즉, her이 he를 포함하는 것도 트라이에서 알 수 있게 된다.

이러한 내용들 때문에 트라이는 접두사 트리(Prefix Tree) 라고도 불린다.

이러한 과정이 이루어 지는동안의 시간 복잡도는 문자열 길이만큼 시간이 들 것이다.

이러한 트라이를 생성해두면, 결국 원하는 단어(원소)를 찾을 때 O(m)의 시간만에 찾아 낼 수 있게 된다.

(이때 m은 문자열 길이를 의미한다.)

이제 처음에 이야기한 내용에 대해 살펴보자.

---

map을 이용하면 충분히 트라이와 같은 효과를 낼 수 있지 않을까??

맵을 이용하면 충분히 트라이와 비슷(?)한 효과를 낼 수 있다.

하지만, 맵의 특성상 이진 검색 트리에서 O(lgN)만큼의 시간이 들 것이고, 그 문자열을 확인하는데

O(MlgN)만큼의 시간이 들 것이기에 map을 이용하는 것과 Trie를 이용하는 것은 엄연히 다른 시간 복잡도를 나타낸다.

---

트라이(Trie)의 단점

그럼 트라이는 문자열을 다룰 때 최강의 자료구조인가요??

답은 그렇지 않고, 상황에 따라 다르다이다.

트라이의 치명적 단점은 공간 복잡도에서 나타난다.

왜 공간 복잡도가 치명적인 단점이 되냐면, 

트라이에서 저러한 O(m)인 시간이 나오기 위해서는 다음 문자를 가리키는 노드가 필요하다.

예를들어 문제에서 숫자에 대해 트라이를 형성해야 한다면 0~9인 총 10개의 포인터 배열을 가져야한다.

또는 알파벳에 대해 트라이를 형성해야 한다면 a~z인 총 26개의 포인터 배열을 가지고 있어야한다.

즉 최종 메모리는 O(포인터 크기 * 포인터 배열 개수 * 트라이에 존재하는 총 노드의 개수)가 된다.

트라이(Trie) 접목하기

이제 실제 문제를 통해 트라이를 이용한 문제를 풀어보자.

[5052번] 전화번호 목록 :: https://www.acmicpc.net/problem/5052

위 문제는 필자가 트라이를 배우기 전 map으로 문제를 해결했던 경험이 있다.

( http://www.crocus.co.kr/818 )

위의 AC는 트라이이고, 아래 AC는 map을 이용하였다.

확실히 메모리와 시간에서 서로가 차이가 나고 있음을 확인할 수 있다.

위의 문제에 대한 소스 코드를 보고 소스 코드를 분석해보자.

소스 코드 : 

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int TrieNode = 10; // 트라이 노드마다 포인터 개수
 
struct Trie 
{
    Trie *next[TrieNode]; // 다음 노드를 가리키는 포인터 배열
    bool finish; // 이 노드에서 끝나는 전화번호가 있는가?
    bool nextChild; // 이 노드의 자식이 있는가?
 
    // 생성자
    Trie() 
    {
        fill(next, next + TrieNode, nullptr);
        finish = nextChild = false;
    }
 
    // 소멸자
    ~Trie() 
    {
        for (int i = 0; i < TrieNode; i++)
            if (next[i])
                delete next[i];
    }
 
    // 문자열 key를 현재 노드부터 삽입. 삽입 후 일관성이 있는지를 리턴
    bool insert(const char *key) 
    {
        // 문자열의 끝이라면
        if (*key == '\0') 
        {
            finish = true;
 
            // 문자열이 끝났는데도
            // 자식이 있다면 일관성이 없다.
            if (nextChild)
                return 0;
            else
                return 1;
        }
 
        int nextKey = *key - '0';
 
        // 다음으로 가는 트라이가 없다면
        if (!next[nextKey])
            next[nextKey] = new Trie;
 
        nextChild = true;
 
        // 여기까지 왔다는 의미는 트라이의 자식이 분명히 있다는것.
        // 이때 자식에서 일관성이 없던게 밝혀지거나
        // finish가 true라면 일관성이 없다는 의미.
        bool get = next[nextKey]->insert(key + 1);
 
        return !finish && get;
    }
};
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while (tc--)
    {
        int n;
        scanf("%d", &n);
 
        // 트라이의 루트 생성
        Trie *root = new Trie;
 
        bool chk = true;
 
        for (int i = 0; i < n; i++)
        {
            char phone[11];
            scanf("%s", phone);
 
            // 일관성이 없다면
            if (chk && root->insert(phone) == 0)
                chk = false;
        }
 
        if (chk)
            printf("YES\n");
        else
            printf("NO\n");
 
        // 트라이 소멸
        delete root;
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

const int TrieNode = 10; // 트라이 노드마다 포인터 개수
 
struct Trie 
{
    Trie *next[TrieNode]; // 다음 노드를 가리키는 포인터 배열
    bool finish; // 이 노드에서 끝나는 전화번호가 있는가?
    bool nextChild; // 이 노드의 자식이 있는가?
 
    // 생성자
    Trie() 
    {
        fill(next, next + TrieNode, nullptr);
        finish = nextChild = false;
    }
 
    // 소멸자
    ~Trie() 
    {
        for (int i = 0; i < TrieNode; i++)
            if (next[i])
                delete next[i];
    }

트라이의 첫번째 부분이다.

TrieNode는 알파벳 혹은 숫자같은 트라이에서 필요로 하는 포인터의 개수이다.

Trie *next[TrieNode]; 는 트라이가 생성될 때 같이 생성되는 포인터 배열을 의미한다.

bool finish는 이 지점에서 끝나는 문자열이 존재하는지 확인해주는 변수이다.

bool nextChild는 이 노드의 자식이 있는지 확인하는 변수이다.

그리고 생성자에서는 모든 포인터를 nullptr로 초기화, finish, nextChild는 false로 초기화한다.

// 문자열 key를 현재 노드부터 삽입. 삽입 후 일관성이 있는지를 리턴
bool insert(const char *key) 
{
    // 문자열의 끝이라면
    if (*key == '\0') 
    {
        finish = true;
 
        // 문자열이 끝났는데도
        // 자식이 있다면 일관성이 없다.
        if (nextChild)
            return 0;
        else
            return 1;
    }
 
    int nextKey = *key - '0';
 
    // 다음으로 가는 트라이가 없다면
    if (!next[nextKey])
        next[nextKey] = new Trie;
 
    nextChild = true;
 
    // 여기까지 왔다는 의미는 트라이의 자식이 분명히 있다는것.
    // 이때 자식에서 일관성이 없던게 밝혀지거나
    // finish가 true라면 일관성이 없다는 의미.
    bool get = next[nextKey]->insert(key + 1);
 
    return !finish && get;
}

이제 트라이에서 가장 중요한 insert부분이다.

문자열의 끝이라 '\0'를 만난다면 finish = true가 될 것이다.

이때 이 문제에서는 일관성을 요구하였기에 finish가 true인데 nextChild가 존재한다면 

her이 이미 있는데 he가 들어왔을때를 의미하는 것과 같은 것이므로 일관성이 없다는 것이다.

(문제에서는 선영의 번호가 91 12 54 26인데 긴급전화가 911이라 일관성이 없다고 하는 것과 같다.)

그리고 nextKey는 *key -'0'로 나타낼 수 있고

현재 nextKey가 있는데 다음으로 가는 포인터 배열이 존재하지 않는다면 트라이를 하나 새로 만들어야 한다.

그리고 nextChild는 true가 될 것이다.

이제 insert 이후 return을 받게 될텐데 이때 일관성이 없다고 판단되었거나, 

자식이 존재하는데 finish가 true였던 경우에는 또 일관성이 없다고 return해주는 방식으로 진행한다.

트라이(Trie) 문제 풀어보기

[14425번] 문자열 집합 :: https://www.acmicpc.net/problem/14425

[5052번] 전화번호 목록 :: https://www.acmicpc.net/problem/5052

[4358번] 생태학 :: https://www.acmicpc.net/problem/4358

[5670번] 휴대폰 자판 :: https://www.acmicpc.net/problem/5670

[3080번] 아름다운 이름 :: https://www.acmicpc.net/problem/3080

[5446번] 용량 부족 :: https://www.acmicpc.net/problem/5446

[13505번] 두 수 XOR :: https://www.acmicpc.net/problem/13505