[Algorithm] 트라이(Trie)

트라이(Trie)

Trie는 탐색트리의 일종으로 특정 문자열이 포함되어있는지 등을 찾는데 효과적인 자료구조다.

 

예를 들어 영어로 된 여러 단어가 N개 주어지고,  여러개의 접두어가 M개 주어진다.

이때, M개의 접두어로 시작하는 단어가 몇 개 있는지 구하는 경우를 생각해보자.

 

단순하게 반복문으로 구하게 되면 (M개의 접두어)*(N개의 단어)*(접두어와 단어를 비교) 의 반복을 하게 된다.

M, N, 접두어 단어의 길이가 작으면 상관없지만 조금이라도 커지면 시간복잡도가 크게 늘어나게 된다.

 

이러한 반복을 줄이는데 효과적인 자료구조가 Trie다.

 

이제 [HILL, HIGH, HELL, HELLO, HELLT] 라는 단어를 Trie 구조로 표현해 보자.

 

그러면 아래 그림과 같이 그릴 수 있다.

 

옆에 있는 빨간색의 숫자는 이러한 단어가 포함된 단어가 몇 개인지 저장 한 것이다.

 

이를 이용하면 접두어가 "HE"인 단어는 3개, "HI"인 단어는 2개 라는 것을 빠르게 찾을 수 있고, 모든 접두어에 대한 개수를 찾는데 걸리는 시간은 접두어의 총 길이의 합과 같게 된다.

​

이제 어떤 식으로 저장이 되는지 그림으로 알아봤으니 실제로 구현해 보자.

 

---

 

Code (char)

 

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

struct Trie {
    int cnt; // 이 문자가 포함된 cnt;
    Trie* children[26];

    //생성자
    Trie() { //초기화
        cnt = 0;
        for (int i = 0; i < 26; i++)
        {
            children[i] = NULL;
        }
    }
    ~Trie()
    {
        for (int i = 0; i < 26; i++)
        {
            if (children[i])
            {
                delete children[i];
            }
        }
    }

    void insert(const char* s)
    {
        cnt += 1;
        if (*s == '\0') {
            return;
        }
        int index = *s - 'A';
        if (children[index] == NULL) {
            children[index] = new Trie();
        }
        children[index]->insert(s + 1);
    }

    int find(const char* s)
    {
        if (*s == '\0') {
            return cnt;
        }
        int index = *s - 'A';
        if (children[index])
        {
            return children[index]->find(s + 1);
        }
        return 0;
    }

};


int main() {
    Trie *trie = new Trie();

    string str[5] = { "HILL", "HIGH", "HELL", "HELLO", "HELLT" };

    for (int i = 0; i < 5; i++) {
        trie->insert(str[i].c_str());
    }
    string answer[4] = { "HE","HI","HELL","HELLO" };
    for (int i = 0; i < 4; i++) {
        cout<<answer[i]<< " : " << trie->find(answer[i].c_str()) << endl;
    }

    return 0;
}

 

위 코드는 char을 이용한 방법이다.

find와 insert를 char로 구현했기 때문에 문자열을 가리키는 char의 포인터를 넘겨준다.

문자열 char의 마지막에는 문자열이 끝났음을 알려주기 위해 마지막에 '\0'이 들어간다.

이를 이용해 마지막 문자열까지 Trie 구조에 저장하는 방법이다.

---

 

+ C++에는 좀 더 편한 string이 있다. string을 사용하면 좀 더 직관적이고 편하게 구현할 수 있다.

 

Code (string)

 

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

struct Trie {
    int cnt; // 이 문자가 포함된 cnt;
    Trie* children[26];

    //생성자
    Trie() { //초기화
        cnt = 0;
        for (int i = 0; i < 26; i++)
        {
            children[i] = NULL;
        }
    }
    ~Trie()
    {
        for (int i = 0; i < 26; i++)
        {
            if (children[i])
            {
                delete children[i];
            }
        }
    }

    void insert(string& str, int idx)
    {
        cnt += 1;
        if (idx == str.length()) {
            return;
        }
        int index = str[idx] - 'A';
        if (children[index] == NULL) {
            children[index] = new Trie();
        }
        children[index]->insert(str, idx + 1);
    }

    int find(string& str, int idx)
    {
        if (idx == str.length()) {
            return cnt;
        }
        int index = str[idx] - 'A';
        if (children[index])
        {
            return children[index]->find(str, idx + 1);
        }
        return 0;
    }

};


int main() {
    Trie* trie = new Trie();

    string str[5] = { "HILL", "HIGH", "HELL", "HELLO", "HELLT" };

    for (int i = 0; i < 5; i++) {
        trie->insert(str[i], 0);
    }
    string answer[4] = { "HE","HI","HELL","HELLO"};
    for (int i = 0; i < 4; i++) {
        cout << answer[i] << " : " << trie->find(answer[i], 0) << endl;
    }

    return 0;
}

---

 

처음 Trie 자료구조를 따라 구현할 때를 생각하면 포인터에 대한 이해도 부족하고 많이 헷갈렸던 것 같다.

이번 기회에 다시 Trie 자료구조를 구현하면서 char외에도 string으로 구현했다.

 

+ 추가 (변수 넘겨주는 방법에 따른 차이)

void func(const char*c){
	c // -> c의 주소 값
    *c // -> c의 value
}

void func2(char &c){
	c // -> c의 값을 참조
    char *p = &c; // c의 pointer
    // func2(*p++) 
}

void func2(char c){
	c // 외부의 c값을 복사해 전달
}