Trie 알고리즘

Trie 알고리즘

Trie 알고리즘이란.

예시를 들어 Tenshi라는 단어를 찾는다고 해보자. 그러면 ‘T’ -> ‘e’ -> ‘n’… 이런 방식으로 순서대로 알파벳을 찾아간다.

그걸 K진트리(알파벳)으로 만들어서 표기한 게 끝이다. 당연히 이론상 depth가 길어질 때마다 소문자 알파벳으로 했을 때는 26의 가짓수씩 분기가 늘어나니 메모리를 많이 먹는다.

다만, 그만큼 한 알파벳마다 그 index에 해당하는 노드로 나아가기만 하면 되므로 O(문자열의 길이)라는 굉장히 짧은 시간 복잡도가 된다.

그것에 대한 백준 14426번에 대한 코드를 보자.

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;

string S;
int result;

struct Trie {
	Trie* ch[26];
	bool end;

	Trie() {
		end = false;
		for (int idx = 0; idx < 26; idx++) {
			ch[idx] = NULL;
		}
	}

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

	void insert(const char* s) {
		if (*s == 0) {
			this->end = true;
			return;
		}

		int now = *s - 'a';

		if (ch[now] == NULL) ch[now] = new Trie;

		ch[now]->insert(s + 1);
	}

	bool find(const char* s) {
		if (*s == 0) return true;

		int now = *s - 'a';

		if (ch[now] == NULL) return false;
		return ch[now]->find(s + 1);
	}
};


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	Trie* root = new Trie;
	for (int idx = 0; idx < N; idx++) {
		cin >> S;
		root->insert(S.c_str());
	}

	for (int idx = 0; idx < M; idx++) {
		cin >> S;
		if (root->find(S.c_str())) result++;
	}
	cout << result;
	return 0;
}

Algorithm 카테고리 내 다른 글 보러가기