> 트라이(Trie)
여튼 또 문자열인데, 이번엔 매칭 문제가 아니라 여러 문자열을 저장하는 자료구조를 소개해드릴 겁니다.
바로 트라이(Trie)인데, 트리와 굉장히 스펠링이 비슷하면서 트리와도 유사합니다. 아니, 아예 트리의 한 종류라고 해도 될 겁니다.
래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 합니다.
예를 들어 {"he", "she", "her", "him", "show"}라는 문자열 집합이 있다면, 그들을 담고 있는 트라이는 그림과 같습니다. 빨간색 겹선 노드가 여기서 끝나는 문자열이 있다는 뜻으로, output이 있다고 하거나 final state, accepting node라고도 하는 등... 그런 의미가 있습니다.
왜 트라이의 별칭 중 접두사 트리라는 것이 있는지도 구조를 보면 파악할 수 있습니다.
여기 저장된 모든 문자열은 루트부터 시작해서 아래로 한 칸씩 내려가며 겹선 노드까지 가며 봐 온 문자를 순서대로 나열한 형태가 됩니다.
예를 들면 "him"이라는 문자열을 찾을 때까지 거쳐가는 경로는 루트->h->i->m인데, 도중에 문자열을 한 글자씩 붙이며 "", "h", "hi", "him"으로 완성됩니다. 이때 도중에 등장하는 문자열은 모두 접두사(prefix)이죠.
또한 집합 중 "he"는 또다른 원소 "her"의 접두사인데, "he"에 도달하는 경로가 "her"에 도달하는 경로에 포함되기도 합니다.
여튼 이제 트라이의 구조는 감이 잡히셨을 겁니다.
저렇게 트라이가 있을 경우 삽입, 탐색에 걸리는 시간은 그 문자열의 길이만큼의 시간이 드리라는 것은 자명합니다(보통 트라이에서 삭제를 하지는 않습니다).
문제는 공간 복잡도입니다. 저런 선형 시간이 나오려면, 찾는 문자열의 다음 글자를 보자마자 맞는 노드로 이동할 수 있어야 합니다.
이렇게 하려면, 영소문자만 단어에 올 수 있을 경우 26칸짜리 포인터 배열을 가지고 있다거나 해야 합니다. 따라서 포인터의 크기 * 26byte 만큼의 메모리가 노드 하나마다 필요하고, 트라이에 존재하는 총 노드 개수를 곱해야겠죠.
당연히 32~127 모든 아스키코드가 존재할 수 있다거나 하면 상황은 더 나빠집니다.
이 때문에 트라이 문제에서는 입력 데이터의 전체 글자 개수는 얼마를 넘지 않는다는 식의 조건을 자주 볼 수 있습니다.
경우에 따라 포인터 배열이 아닌 set(BST)으로 구현할 수도 있습니다.
- BOJ[5052] : 전화번호 목록
https://www.acmicpc.net/problem/5052
이 문제가 트라이 문제 중 가장 쉽고, 트라이의 성질을 잘 사용하는군요.
문제를 읽어보시면 전화번호를 단어라고 했을 때, 영소문자 대신 숫자만 등장하는 경우입니다.
전화번호들을 모두 하나의 트라이에 저장할 것인데, 전화번호가 최대 만 개고 각각 10자리 이하이므로 등장하는 글자 개수는 최대 10만 개 이하라고 짐작할 수 있습니다.
일관성이 있다의 기준을 트라이만으로 해결할 수 있을까요?
아까 접두사 트리라는 이름과 트라이의 연관성을 살짝 설명해드린 것이 힌트가 됩니다.
첫 번째 예제입니다. 일관성이 없죠.
두 번째 예제는 일관성이 있습니다.
일관성이 있으려면, 그 어떤 전화번호도 다른 전화번호의 접두사가 되는 일이 없어야 합니다.
그 말인 즉슨, 트라이의 관점에서 보자면 아까처럼 어떤 전화번호로 가는 경로에 다른 전화번호의 경로가 완전히 포함되면 안 된다는 겁니다.
전화번호의 끝 노드를 accepting node라고 하면, 모든 accepting node가 자식 노드를 가지지 않으면 일관성이 있게 됩니다.
그럼, 트라이를 구현해 봐야겠죠.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int GO_MAX = 10; // 트라이 노드마다 포인터 개수
struct Trie{
Trie* go[GO_MAX]; // 다음 노드를 가리키는 포인터 배열
bool output; // 이 노드에서 끝나는 전화번호가 있는가?
bool goexist; // 이 노드의 자식이 있는가?
// 생성자
Trie(){
fill(go, go+GO_MAX, nullptr);
output = goexist = false;
}
// 소멸자
~Trie(){
for(int i=0; i<GO_MAX; i++)
if(go[i]) delete go[i];
}
// 문자열 key를 현재 노드부터 삽입
void insert(const char* key){
// 문자열이 끝남
if(*key == '\0') output = true;
// 아닐 경우
else{
int next = *key - '0';
// 해당 노드가 없으면 새로 동적 할당해서 만듦
if(!go[next]) go[next] = new Trie;
goexist = true;
// 자식 노드에서 이어서 삽입
go[next]->insert(key+1);
}
}
// 이 노드가 일관성이 있는가?
bool consistent(){
// 자식도 있으면서 여기서 끝나는 전화번호도 있다면 일관성 없음
if(goexist && output) return false;
// 자식들 중 하나라도 일관성이 없으면 이 노드도 일관성이 없음
for(int i=0; i<GO_MAX; i++)
if(go[i] && !go[i]->consistent()) return false;
// 일관성이 있음
return true;
}
};
int main(){
int T;
scanf("%d", &T);
for(int t=0; t<T; t++){
int N;
scanf("%d", &N);
Trie *root = new Trie; // 루트 노드 만들기
for(int i=0; i<N; i++){
char tel[11];
scanf("%s", tel);
root->insert(tel);
}
puts(root->consistent() ? "YES" : "NO");
// 소멸자를 호출하여 동적 할당 해제를 하지 않으면 힙 메모리가 부족할 수 있음
delete root;
}
}제가 자주 사용하는 방식입니다. 각 노드를 필요할 때 동적 할당하는 방법이죠.
트라이 구조체 부분에서 consistent() 함수를 제외하고 보면 트라이 기본 구조를 알 수 있습니다.
이 문제에서 필요한 consistent() 함수의 경우 이 노드로부터 도달할 수 있는 전화번호들의 목록이 일관성이 있는지를 bool 타입으로 반환합니다.
트라이 또한 트리 구조이기 때문에 거의 모든 연산이 재귀호출의 형태를 띕니다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int GO_MAX = 10; // 트라이 노드마다 포인터 개수
struct Trie{
Trie* go[GO_MAX]; // 다음 노드를 가리키는 포인터 배열
bool output; // 이 노드에서 끝나는 전화번호가 있는가?
bool goexist; // 이 노드의 자식이 있는가?
// 생성자
Trie(){
fill(go, go+GO_MAX, nullptr);
output = goexist = false;
}
// 소멸자
~Trie(){
for(int i=0; i<GO_MAX; i++)
if(go[i]) delete go[i];
}
// 문자열 key를 현재 노드부터 삽입. 삽입 후 일관성이 있는지를 리턴
bool insert(const char* key){
if(*key == '\0'){
output = true;
return !goexist; // 만약 자식이 있다면 일관성이 없다
}
int next = *key - '0';
if(!go[next]) go[next] = new Trie;
goexist = true;
// 여기까지 온 시점에서 자식이 분명히 있는데, 여기서 끝나는 전화번호가 있다면 일관성이 없다
return !output && go[next]->insert(key+1);
}
};
int main(){
int T;
scanf("%d", &T);
for(int t=0; t<T; t++){
int N;
scanf("%d", &N);
Trie *root = new Trie; // 루트 노드 만들기
bool result = true;
for(int i=0; i<N; i++){
char tel[11];
scanf("%s", tel);
// insert 함수가 일관성이 유지되는지를 즉각 리턴함
if(result && !root->insert(tel)) result = false;
}
puts(result ? "YES" : "NO");
// 소멸자를 호출하여 동적 할당 해제를 하지 않으면 힙 메모리가 부족할 수 있음
delete root;
}
}헌데 트라이 구조를 잘 이해하셨다면 마지막이 아니라 그냥 삽입 도중에 답을 알 수도 있습니다.
어쨌거나 어떤 노드에서 끝나는 문자열과 자식이 동시에 있느냐만 알면 되니까,
삽입을 하는 도중에 그 경우가 일어나는지를 바로 체크해서 재귀함수를 통해 리턴하게 할 수 있습니다.
이 트라이 구조체의 경우 goexist와 output이 둘 다 true면 일관성이 없게 됩니다.
#include <cstdio>
#include <cstring>
using namespace std;
const int GO_MAX = 10; // 트라이 노드마다 포인터 개수
const int CHAR_MAX = 100000; // 트라이의 최대 글자 개수
struct Trie{
int cnt; // 노드의 개수
int go[CHAR_MAX+1][GO_MAX]; // 다음 노드 번호를 담고 있는 배열
bool output[CHAR_MAX+1]; // 이 노드에서 끝나는 전화번호가 있는가?
bool goexist[CHAR_MAX+1]; // 이 노드의 자식이 있는가?
// 생성자
Trie(){
cnt = 1;
memset(go, 0, sizeof(go));
memset(output, 0, sizeof(output));
memset(goexist, 0, sizeof(goexist));
}
// 문자열 key를 현재 노드부터 삽입. 삽입 후 일관성이 있는지를 리턴
bool insert(const char* key, int node = 0){ // 루트의 번호는 0
if(*key == '\0'){
output[node] = true;
return !goexist[node]; // 만약 자식이 있다면 일관성이 없다
}
int next = *key - '0';
if(!go[node][next]) go[node][next] = cnt++;
goexist[node] = true;
// 여기까지 온 시점에서 자식이 분명히 있는데, 여기서 끝나는 전화번호가 있다면 일관성이 없다
return !output[node] && insert(key+1, go[node][next]);
}
};
int main(){
int T;
scanf("%d", &T);
for(int t=0; t<T; t++){
int N;
scanf("%d", &N);
Trie trie; // 트라이 자료 구조
bool result = true;
for(int i=0; i<N; i++){
char tel[11];
scanf("%s", tel);
// insert 함수가 일관성이 유지되는지를 즉각 리턴함
if(result && !trie.insert(tel)) result = false;
}
puts(result ? "YES" : "NO");
}
}또한, 동적 할당이 영 내키지 않으신다면 입력의 최대 문자 개수를 알 때 동적 할당 없이도 구현이 가능합니다.
위 코드는 Trie 구조체가 노드 하나가 아닌, 자료구조 하나를 구현하고 있는데요.
노드가 하나 생길 때마다 0, 1, 2, 3, ... 등의 번호를 순차적으로 부여하면서, go, output, goexist 값들을 전체 배열 하나로 통합합니다. 루트는 보통 0번입니다.
-BOJ[5670] Cellphone Typing
https://www.acmicpc.net/problem/5670
정말 미친듯이 트라이스러운 문제입니다.
문제는 상당히 긴 편이지만 꽤 직관적이라서 이해하는 게 어렵지는 않으실 겁니다.
추천 단어들이 있는 사전이 있고, 추천 단어들만을 타이핑하고 싶을 때 자판기가 단어 완성을 100% 정확한 경우에만 바로바로 해주는 것인데요.
예를 들어 사전에 {"abc", "abcd", "xyz"}가 있다면 자판기에서 'a'를 타이핑하는 순간 a로 시작하는 모든 추천 단어는 "abc"로도 시작하므로 "abc"까지 자동 타이핑이 됩니다.
여기서 입력을 멈추면(멈추는 것은 별도의 타이핑 횟수로 세지 않습니다) "abc"가 입력되고, "d"를 더 치면 "abcd"가 입력되는 셈입니다.
즉 "abc"는 단 1번의 타이핑, "abcd"는 2번의 타이핑으로 끝낼 수 있습니다.
마찬가지로 맨 처음에 'x'를 타이핑하면 x로 시작하는 단어가 "xyz"뿐이고, 따라서 "x"로 시작하는 모든 단어는 "xyz"로도 시작하니까 "xyz"까지 자동 완성이 되고, "xyz"는 1번의 타이핑만으로 입력할 수 있습니다.
이때 사전 내의 모든 단어의 평균 타이핑 횟수를 구하는 것인데, 재귀호출로 구할 수 있어 보입니다.
확인차 첫 번째 예제를 트라이로 그려보면 위와 같습니다.
현재 노드의 서브트리 안에서 등장하는 문자열들을 치는 데 추가로 필요한 평균/총 타이핑 횟수를 구해서 반환해 주는 재귀 함수를 트라이에서 구현하면 풀 수 있습니다.
저는 일단 총 타이핑 횟수를 구한 후 마지막에 전체 단어 개수로 나누겠습니다.
가장 먼저 낼 수 있으면서 핵심이 되는 아이디어는, 어떤 노드의 자식이 단 하나뿐이라면 자동완성으로 현재 글자가 타이핑될 것이라는 점입니다.
이런 글자가 연속적으로 나타난다면 전부다 자동 타이핑으로 넘어가겠죠.
만약 자동완성이 되지 않는다면, 해당 노드 서브트리에 속한 단어 개수만큼 총 타이핑 횟수가 필요할 겁니다.
또한 문제 조건에도 있듯이 루트에서는 자동완성이 안 됩니다. 즉 맨 첫 글자는 반드시 타이핑해야 합니다.
#include <cstdio>
#include <algorithm>
using namespace std;
struct Trie{
Trie *go[26];
bool output;
int branch; // 가지, 즉 자식 노드의 개수
int words; // 현재 노드 서브트리에 있는 단어의 개수
// 생성자
Trie(): output(false), branch(0), words(0){ fill(go, go+26, nullptr); }
// 소멸자
~Trie(){
for(int i=0; i<26; i++)
if(go[i]) delete go[i];
}
// 트라이에 단어를 삽입하는 함수
void insert(char *str){
if(*str == '\0'){
branch++;
output = true;
}
else{
if(!go[*str-'a']){
branch++;
go[*str-'a'] = new Trie;
}
words++;
go[*str-'a']->insert(str+1);
}
}
// 현재 노드에서 더 필요한 총 타이핑 횟수를 세는 재귀 함수
long long cntKeystrokes(bool isRoot=false){
long long result = 0;
// 맨 처음이거나, 현재로부터 도달가능한 단어가 2개 이상이면 속한 단어 개수만큼 타이핑++
// 바꿔 말하면, 위 경우가 아니면 타이핑이 필요없다
if(isRoot || branch > 1) result = words;
// 각 자식들의 결과를 모두 더해서 반환
for(int i=0; i<26; i++)
if(go[i]) result += go[i]->cntKeystrokes();
return result;
}
};
int main(){
int N;
while(scanf("%d", &N) > 0){
Trie *root = new Trie;
for(int i=0; i<N; i++){
char W[81];
scanf("%s", W);
root->insert(W);
}
printf("%.2lf\n", 1.0*root->cntKeystrokes(true)/N);
delete root;
}
}문제에 따라 트라이에서 노드마다 저장해 두어야 하는 값이 다양하게 변합니다.
위 전략대로 풀 경우 각 노드마다 현재 노드의 서브트리에 존재하는 단어 개수(words)를 담고 있으면 정말 좋을 것입니다.
트라이 응용 문제들은 예제로 트라이를 그려 보고 규칙을 관찰하다 보면 풀리는 경우가 많습니다.
다들 공책을 상비합시다!
트라이 관련 추천문제
14425번: 문자열 집합
메모리 1536 MB의 압박은 총 500만개의 노드를 다 저장하고서라도 트라이를 써보라는 말입니다. 저런 메모리 제한은 처음 보네요...
그러나 사실은 이 문제는 그냥 해싱(ounrdered_set)으로도 충분히 풀립니다.
5052번: 전화번호 목록
위에서 설명한 문제입니다.
4358번: Hardwood Species
문제 자체는 정말 쉽습니다. 그냥 각 나무마다 전체 나무들 중 얼마나 분포하는지를 % 단위로 세면 되는데요, 이건 output을 bool type 대신 카운팅 변수로 써서 전체 나무 개수로 나누면 쉽게 구할 수 있습니다.
단, 정말 어이가 없는 함정이 있는데 나무 이름에 영어와 공백뿐 아니라 특수문자도 들어갑니다. 32~127 사이의 아스키코드를 전부 사용합니다;;
5670번: Cellphone Typing (★)
위에서 설명한 문제입니다.
3080번: 아름다운 이름 (★)
문제의 규칙을 잘 관찰해 보면, 어떤 노드가 있을 때 그 노드의 서브트리에 속한 이름들을 정렬하는 방법은 순열과 관련이 있습니다.
첫 번째 예제를 봅시다. IVO는 첫 번째나 세 번째 자리에만 올 수 있는데 이는 J로 시작하는 두 이름이 반드시 붙어있어야 하기 때문입니다. J로 시작하는 두 이름의 순서는 상관이 없습니다.
따라서 IVO를 앞에 배치하느냐 뒤에 배치하느냐(2) * J로 시작하는 두 이름의 배치(2)의 경우의 수를 곱해 4가 됩니다.
두 번째 예제에서 "MARA", "MARICA", "MARTA", "MARTINA" 이 4개는 반드시 붙어 있어야 하는데 이는 모두다 "MAR"로 시작하기 때문. 따라서 그렇지 않은 "MATO"는 반드시 이 5개의 단어 중 맨 앞이나 뒤에 와야 합니다(*2).
그 다음, 저 "MAR"로 시작하는 4개의 단어들 중에서 "MART"로 시작하는 단어 2개는 반드시 붙어 있어야 하고 나머지 순서는 상관이 없죠. 이때 "MAR"로 시작하는 단어들 중 "MAR" 다음 글자는 'A', 'I', 'T' 총 3개이므로 이때 경우의 수는 순열 3P3 = 3!이 됩니다.
마지막으로 "MART"로 시작하는 두 단어의 순서는 상관없으므로 _2. 따라서 답이 2_6_2=*_24**입니다.
규칙을 일반화하면 어떤 노드에서 공백을 포함하여 존재하는 다음 글자의 개수가 k이면 k!만큼의 경우의 수를 곱해 주는 식으로 결과를 구할 수 있습니다.
5446번: The Great Cleanup (★)
"rm ~~*" 형식의 명령어를 최소 횟수로 써서 지워야 하는 파일을 모두 지워야 합니다. 이때, 지우면 안 되는 파일도 있어서 골치아프죠.
형식에서 애스터리스크가 반드시 맨 끝에만 올 수 있기 때문에 접두사를 매우 잘 써먹을 수 있게 되고 이는 곧 트라이를 사용한다는 아이디어로 직결됩니다.
어떤 노드에 도달하는 문자열이 P라고 합시다. 이때 "rm P*"를 사용할 수 있는 경우는 P로 시작하는 파일 중 지우면 안 되는 파일이 하나도 없을 경우입니다.
따라서 각 노드마다 이 노드 서브트리에 지워야 하는 파일이 존재하는지와 지우면 안 되는 파일이 존재하는지를 bool 변수로 저장해두는 것이 유용합니다. 그리고 각 노드마다 P로 시작하는 파일들을 모두 지우는 데 필요한 최소연산횟수를 재귀호출로 구하면 해결할 수 있습니다.
재귀함수를 모델링했다면 다음과 같은 3가지 경우가 생깁니다.
P로 시작하는 지워야 하는 파일이 하나도 없다면 연산이 아예 필요없습니다! 이때는 바로 0을 리턴합니다.
P로 시작하는 지우면 안 되는 파일이 하나도 없다면 "rm P*"를 사용해서 모든 파일을 지울 수 있으므로 바로 1을 리턴합니다.
이도저도 아닐 경우 자식들을 재귀호출에 결과를 모두 더하면 되겠죠. 이때 주의할 점은, 파일명이 P인 파일이 존재할 경우 이걸 지우기 위해 "rm P"를 한 번 써야 합니다! 따라서 노드의 output 값을 보고 1을 더해 줘야 합니다.
'알고리즘 > [ 개념 ]' 카테고리의 다른 글
| [ 개념 ] 50. Levenshtein(편집 거리) 알고리즘 (2) | 2021.03.30 |
|---|---|
| [ 개념 ] 49. LCS(Longest Common Subsequence) (0) | 2021.03.29 |
| [ 개념 ] 47. 스위핑 알고리즘(Sweeping Algorithm) (0) | 2020.09.22 |
| [ 개념 ] 46. 레이지 프로퍼게이션(Lazy Propagation) (0) | 2020.09.22 |
| [ 개념 ] 45. 볼록 껍질(Convex Hull) (0) | 2020.09.22 |