[Algorithm] 트라이(Trie) 개념과 기본 문제

C++에서 트라이(Trie)를 구현해보고 기본 문제를 풀어보자.

환경

트라이(Trie)란?

트라이(Trie)의 형태 대해서

Trie: 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.
위에 보이는 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있습니다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있습니다.
DFS 형태로 검색을 해보면 사진의 번호에 나와있듯이 to, tea, ted, ten, A, i, in, inn이라는 단어들이 자료구조에 들어가 있음을 알 수 있습니다.

트라이(Trie)의 예시

직접 그린 Trie이며 주황색으로 된 노드들이 입력된 문자열들입니다.
현재 be, bee, can, cat, cd가 들어가 있습니다.

사용목적

목적

사용하는 이유는 문자열의 탐색을 하고자할 때 시간복잡도를 보면 알 수 있습니다. 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적입니다. 단, 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있습니다.
검색어 자동완성, 사전에서 찾기 그리고 문자열 검사 같은 부분에서 사용할 수 있다고 첨부된 자료에 나와있습니다.

시간 복잡도

제일 긴 문자열의 길이를 L 총 문자열들의 수를 M이라 할 때 시간복잡도는 아래와 같습니다.
생성시 시간복잡도: O(M*L), 모든 문자열들을 넣어야하니 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서 O(M*L)만큼 걸립니다. 물론 삽입 자체만은 O(L)만큼 걸립니다.
탐색시 시간복잡도: O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L)만큼 걸립니다.

트라이(Trie)의 구현

공통

알파벳 대문자를 기준으로 만들었습니다.

#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}

트라이(Trie) 코드

is_terminal: 단어의 끝임을 표시하는 변수입니다.
void insert(const char * key): 새로운 문자열을 트라이에 추가하는 코드입니다.
Trie* find(const char * key): key에 해당하는 문자열을 접두어로 가지고 있는지 확인하고 가지고 있다면 해당 접두어가 끝나는 부분의 위치를 반환합니다.
bool string_exist(const char * key): key에 해당하는 문자열이 포함되어 있는지 확인하는 코드입니다. 해당 key의 문자열이 있다면 true를 반환하고 없으면 false를 반환합니다.

struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie(): is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};

메인함수

해당 함수들이 다 올바르게 작동하는지 확인하는 코드를 작성하였습니다.

int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert: %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s: be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s: c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}

전체코드

#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}

struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie(): is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};

int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert: %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s: be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s: c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s: c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s: cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}

트라이(Trie)를 이용한 기본 문제

백준 온라인 저지 5052번

전화번호 목록이 주어질 때 해당 번호들이 일관성이 있는지 확인하는 코드로 일관성이 있으면 YES를 없으면 NO를 출력하는 문제
전화번호 목록들 중에 어떠한 번호가 다른 번호의 접두어가 되면 일관성이 없다고 판단한다. 다시 말해 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
링크: https://www.acmicpc.net/problem/5052

풀이 및 접근

문자열을 처리하는 문제이며 나아가 접두어를 이용한 자료구조를 만들어야하기 때문에 트라이(Trie)를 사용해야함을 알 수 있습니다.
방법1: 트라이에 모든 번호들을 저장하고 탐색하면서 문자열이 끝나기전에 is_terminal이 나오면 접두어가 존재하는 것이기 때문에 false를 반환해서 판단해줍니다.
방법2: 트라이에 번호들을 추가하면서 현재 주어진 번호가 다른 번호의 접두어가 되는지 바로 판단합니다.

풀이 코드

방법1

트라이에 모든 번호들을 저장하고 탐색하면서 문자열이 끝나기전에 is_terminal이 나오면 접두어가 존재하는 것이기 때문에 false를 반환해서 판단해줍니다.

#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];
	Trie(): is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	void insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
		}
		else {
			int index = char_to_index(*key);
			if (next[index] == 0)
				next[index] = new Trie();
			next[index]->insert(key + 1);
		}
	}

	bool find(const char * key) {

		if (*key == '\0') return true;

		// Return false if there is already terminal node before string is the end.
		if (is_terminal) return false;

		int index = char_to_index(*key);
		return next[index]->find(key + 1);
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();
		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);
			root->insert(phone_books[i]);
		}

		bool is_valid = true;
		for (int i = 0; i < n; ++i) {

			if (root->find(phone_books[i]) == false) {
				is_valid = false;
				break;
			}
		}
        delete root;
		printf("%s\n", is_valid ? "YES" : "NO");
	}
	return 0;
}

방법2

트라이에 번호들을 추가하면서 현재 주어진 번호가 다른 번호의 접두어가 되는지 바로 판단합니다.

#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];

	Trie(): is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	bool insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
			return true;
		}
		else {
			// If it is already terminal node then there is a prefix match
			if(is_terminal == true) return false;

			int index = char_to_index(*key);

			if (next[index] == 0)
				next[index] = new Trie();

			// If next node is already exists and current's next is end of string then there is a prefix match
			else if(next[index] != 0 && *(key + 1) == '\0'){
				return false;
			}
			return next[index]->insert(key + 1);
		}
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();

		bool ret = true;

		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);

			if (ret == false) continue;

			ret = root->insert(phone_books[i]);

		}

		delete root;
		printf("%s\n", ret ? "YES" : "NO");
	}
	return 0;
}

Categories

Tags

Posts

About

Home

[Algorithm] 트라이(Trie) 개념과 기본 문제

August 04, 2019

[Algorithm] 트라이(Trie) 개념과 기본 문제

환경

트라이(Trie)란?

트라이(Trie)의 형태 대해서

트라이(Trie)의 예시

사용목적

목적

시간 복잡도

트라이(Trie)의 구현

공통

트라이(Trie) 코드

메인함수

전체코드

트라이(Trie)를 이용한 기본 문제

백준 온라인 저지 5052번

풀이 및 접근

풀이 코드

방법1

방법2

참고자료

[UML] 유스 케이스 다이어그램(Use Case Diagram)

[UML](EN) Use Case Diagram

[회고] 회고를 해보자