[자료구조] 트라이(Trie) 자료구조

 

[목차]

 

1. 트라이(Trie) 자료구조란?

 

2. 트라이(Trie)의 작동 원리

 

3. 트라이(Trie) 자료구조의 장/단점

 

4. 트라이(Trie) 자료구조의 구현

 

5. 트라이(Trie) 예제 문제

 

 

  1. 트라이(Trie) 자료구조란?

 

트라이(Trie)는 문자열의 집합을 표현하는 '트리 자료구조'이다. 

원하는 원소를 찾기 위해 자주 이용되는 이진 검색 트리 (STL set, map) 등에서는 원소를 찾는데 O(logN)의 시간이 걸리게 된다. 

하지만, 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에 

원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다. 

따라서 여러 번 이 작업을 수행한다면 시간이 오래 걸릴 것이다.

 

이 단점을 해결하기 위한 문자열 특화 자료구조가 트라이(Trie)이다. 

쉽게 말해, "문자열을 빠르게 탐색할 수 있는 자료구조"이다.

 

(본문에서 나오는 M은 문자열의 길이를 의미한다)

 

 

  2. 트라이(Trie)의 작동 원리

우선 그림을 통해서 먼저 살펴보자. 

다음 그림은 문자열 집합 {"rebro", "replay", "hi" , "high", "algo"} 를 트라이로 구현한 것이다. 

 

이처럼, 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다. 

한 문자열에서 다음에 나오는 문자가 현재 문자의 자식 노드가 되고, 빨간색으로 나타낸 노드는 문자열의 끝을 의미한다.

그렇다면 트라이 구조가 문자열을 탐색하기 위한 자료구조이므로, 문자열을 탐색하기 위해서는 다음 글자에 해당하는 노드가 연결되어 있는지, 연결되어 있다면 그 노드를 타고 계속해서 따라가야 할 것이다. 

그리고 문자열의 끝에 도달했을 때, 해당 노드에서 끝나는 문자열(빨간 노드)이 있다면 찾고자 하는 문자열이 집합에 포함되어 있는 것이다. 

잘 이해해보면, 문자열의 끝을 나타내는 빨간 노드는 항상 하나의 문자열의 끝을 의미하게 되는 것을 알 수 있다.

 

그리고, 트라이의 중요한 속성 중 하나는, 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻을 수 있다는 것이다. 

예를 들어서 "rebro"를 찾는다고 해보자. 

r -> re -> reb -> rebr -> rebro가 되므로 "rebro"의 모든 접두사들이 다 구해지게 된다.

따라서 각 노드에는 접두사를 저장할 필요 없이, 문자 하나만 저장해둬도 충분하게 된다. 

 

 

 

  3. 트라이(Trie) 자료구조의 장/단점

트라이의 장점은 앞에서도 언급했듯이 당연히 문자열을 빠르게 찾을 수 있다는 점이다. 

더불어, 문자열을 집합에 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에 

문자열의 추가와 탐색 모두 O(M)만에 가능하다.

 

반면에 트라이의 단점은 필요한 메모리의 크기가 너무 크다는 점이다. 

문자열이 모두 영소문자로 이루어져 있다고 해도, 자식 노드를 가리키는 26개의 포인터를 저장해야 한다. 

최악의 경우에는 집합에 포함되는 문자열들의 길이의 총합만큼 노드가 필요하므로, 총메모리는

O(포인터 크기 * 포인터 배열 개수 * 총노드의 개수)가 된다. 

만약, 1000자리의 문자열이 1000개만 들어온다고 하더라도 100만 개의 노드가 필요하고, 포인터의 크기가 8byte라고 하면 약 200MB의 메모리가 필요하게 된다. 

 

따라서, 이 단점을 해결하기 위해서 보통 map이나 vector를 이용하여 필요한 노드만 메모리를 할당하는 방식들을 이용하는데, 문제에 따라서 메모리 제한이 빡빡한 경우에는 최적화가 꽤나 까다롭다. 

또한, 문제에서 주어진 조건을 보고 트라이를 이용할 수 있는 문제인지 파악하는 것도 중요하다.

 

 

  4. 트라이(Trie) 자료구조의 구현

 

트라이의 한 노드를 구성하는 객체는 자손 노드를 가리키는 '포인터 목록'과, 문자열의 끝인지를 나타내는 '불린 값 변수'로 구성된다. 

 

struct Trie {
	Trie* ch[26];
   	//map<char, Trie*> ch; 맵을 이용하는 경우
   	//vector<pair<char, Trie*>> ch; 벡터를 이용하는 경우
	bool end; 
}

보통은 영소문자 또는 영대문자로만 이루어진 경우가 많기 때문에 Trie* ch[26]과 같이 포인터 배열을 선언한다.

만약 메모리 최적화나, 필요한 노드만 추가하고 싶다면 map이나 vector를 이용한다. 

 

동적으로 트라이를 할당해주기 때문에 메모리 해제 또한 중요하다.

다음은 생성자와 소멸자이다. 

 

Trie() {
	end = false;
	for (int i = 0; i < 26; i++) ch[i] = NULL;
}
~Trie() {
	for (int i = 0; i < 26; i++) if (ch[i]) delete ch[i];
}

 

이제, 문자열을 트라이에 넣어주는 함수가 필요하다. 

이미 트라이에 다음 문자에 해당하는 노드가 있는 경우에는 해당 노드를 그대로 따라가면 되고,

만약 없는 경우에는 새로 노드를 만들어서 해당 노드를 따라간다.

그리고 문자열의 끝에 도착한 경우에는 끝을 나타내는 boolean 변수를 true로 설정한다.

string으로 문자열을 선언했다면, insert함수에 넣어줄 때 C 스타일의 문자열로 바꿔서 넣어줘야 하는 점을 주의하자.

(문자열의 끝에 도달했는지를 쉽게 파악할 수 있다)

 

void insert(const char* s) {
	if (!*s) {
		this->end = true;
		return;
	}
	int now = *s - 'A';
	if (!ch[now]) ch[now] = new Trie;
	ch[now]->insert(s + 1);
}

 

다음은, 트라이에 찾고자 하는 문자열이 있는지를 탐색하는 함수이다.

만약 다음 문자로 가는 노드가 현재 노드의 자손으로 존재하지 않는다면, 탐색에 실패한 경우이다.

계속 탐색하다가 문자열의 끝에 도착했을 때 해당 노드의 boolean 변수가 TRUE라면, 탐색에 성공한 경우이다.

 

bool find(const char* s) {
	if (!*s) {
		if (end) return true;
		return false;
	}
	int now = *s - 'A';
	if (!ch[now]) return false;
	return ch[now]->find(s + 1);
}

 

최종적으로 아래와 같이 트라이가 구현된다.

 

#include<bits/stdc++.h>
using namespace std;
struct Trie {
	Trie* ch[26];
	bool end;
	Trie() {
		end = false;
		for (int i = 0; i < 26; i++) ch[i] = NULL;
	}
	~Trie() {
		for (int i = 0; i < 26; i++) if (ch[i]) delete ch[i];
	}
	void insert(const char* s) {
		if (!*s) {
			this->end = true;
			return;
		}
		int now = *s - 'A';
		if (!ch[now]) ch[now] = new Trie;
		ch[now]->insert(s + 1);
	}
	bool find(const char* s) {
		if (!*s) {
			if (end) return true;
			return false;
		}
		int now = *s - 'A';
		if (!ch[now]) return false;
		return ch[now]->find(s + 1);
	}
};
int main(void) {
	Trie* root = new Trie;
	string s;
	root->insert(s.c_str());
	string tmp = "AAA";
	if (root->find(tmp.c_str())) cout << "Find!";
	else cout << "No";
	delete root;
}

 

 

 

  5. 트라이(Trie) 예제 문제 (풀이 작성 중)

'더보기'를 누르면 풀이가 나옵니다.

(난이도 20.12.13 Solved.ac 기준)

 

[백준 5052번] 전화번호 목록  Gold IV

트라이의 기본 문제이다. 트라이에 모두 전화번호를 넣어놓고, 어떤 노드가 끝나는 문자열이 있고, 자식이 있다면 일관성이 없는 목록이다.

 

[백준 14725번] 개미굴  Gold II

일반적인 트라이와는 다르게, 노드에 문자가 아닌 문자열을 넣는 것이 핵심이다. 

 

[백준 5670번] 휴대폰 자판  Platinum III

버튼을 언제 입력해야 하는지를 파악하는 것이 중요하다. 

노드를 따라가다가 자손이 하나밖에 없거나, 자손이 있고 현재 노드에서 끝나는 문자열이 있는 경우에 버튼을 입력해야 한다.

 

전체 풀이 : wogud6792.tistory.com/87

 

[백준 9202번] Boggle  Platinum V

시간이 10초로 널널하다. 나올 수 있는 모든 경우의 수를 직접 다 구해도 충분할 것 같다.

 

전체 풀이 : wogud6792.tistory.com/88

 

[백준 13505번] 두 수 XOR  Platinum III

풀이)

 

[백준 5446번] 용량 부족  Platinum III

풀이)

 

[백준 3080번] 아름다운 이름  Platinum II

풀이)

 

[백준 17365번] 별다줄  Platinum III

풀이)

 

[백준 13504번] XOR 합  Platinum III

풀이)

 

[백준 16903번] 수열과 쿼리 20  Platinum II

풀이)

 

[백준 16902번] mex  Platinum II

풀이)

 

[백준 19585번] 전설  Platinum III

풀이)