원하는 원소를 찾기 위해 자주 이용되는 이진탐색트리(set, map) 등에서 원소를 찾는 데에 O(logN)의 시간이 걸린다. 하지만, 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에 원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다. 따라서 여러 번 이 작업을 수행한다면 시간이 오래 걸릴 것이다. 이 단점을 해결하기 위한 문자열 특화 자료구조가 트라이(Trie)이다.
Trie
트라이
- 문자열에 특화된 자료구조로, 문자열의 집합을 표현하는 트리 자료구조
- Retrieval(탐색)에서 trie를 따온 용어이다. 맨 앞의 접두어(prefix)부터 시작하여 단어 전체를 찾아가는 과정이므로 접두사 트리(Prefix-Tree) 라고도 한다.
-
영어사전의 방식을 그대로 차용한다.
ex) game 단어 탐색 → 사전에서 g를 찾고 순서대로 a, m, e를 찾는데, 이를 트리형식으로 구현한 것이 trie
- 길이가 m인 문자열을 O(m)에 찾을 수 있다.
- 트라이(Trie)는 문자열 저장을 위한 공간을 많이 쓰지만 탐색에 매우 효율적이라는 특징이 있다.
💡 문자열 탐색 방법
1. 단순 비교
- 전체 문자열의 맨 처음부터 끝까지 개별 문자를 비교하는 방식
- 최대 문자열 길이가 m, 전체 문자 개수가 n개일 경우, worst-case : O(mn)
2. 이진 탐색 기법
- 전체 문자열을 사전 순으로 배열 저장한 후, 중간값과 비교하여 사전적으로 이전이면 좌측, 이후면 우측으로 비교하는 것을 반복하는 방식
- 최대 문자열 길이가 m, 전체 문자 개수가 n개일 경우,
정렬 : O(nmlogn), 탐색 : O(mlogn) → O(nmlogn)
3. 트라이
- K-진 트리 구조를 통해 문자열 저장하는 방식
- 최대 문자열 길이 m 일 때 문자의 개수와 무관하게 시간복잡도는 O(m)
- 각 문자 하나를 배열의 위치로 지정하여 문자열 하나 찾을 때 O(1)이므로 길이만큼의 시간만 소요함
- 만약, 문자열 길이가 너무 커서 Map 등을 이용해 동적할당을 해야 하는 경우 O(mlogn) 만큼 소요할 수 있다.
Trie의 구조
루트 노드는 어떠한 단어도 가지지 않고 루트 노드의 아래부터 문자열의 접두사(prefix) 가 하나씩 이어지게 된다. 이러한 특징때문에 Trie는 접두사 트리(Prefix Tree)라고 불리는 것이다.
 |
|---|
| {“rebro”, “replay”, “hi” , “high”, “algo”} |
위 그림에서 빨간색 노드는 문자열의 말단을 의미한다. 즉, 루트 노드의 자식 노드부터 빨간색 노드까지의 접두사들이 모여 하나의 단어를 이루는 것이다.
그리고, 트라이의 중요한 속성 중 하나는, 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻을 수 있다는 것이다.
예를 들어서 "rebro"를 찾는다고 해보자. r -> re -> reb -> rebr -> rebro가 되므로 “rebro”의 모든 접두사들이 다 구해지게 된다. 따라서 각 노드에는 접두사를 저장할 필요 없이, 문자 하나만 저장해둬도 충분하게 된다.
Trie의 구현
각각의 노드들에 자식 노드를 저장시켜 놓고 단어를 탐색한다. 보통 파이썬으로 구현할 때는 dictionary를 활용해 구현한다.
{”ab”, “abc”, “car”}를 저장해보자.
✏ Step 1. abc 추가
1) 빈 Head의 자식노드에 “a”를 추가한다. 2) “a”노드에 자식이 하나도 없음으로, “b”를 자식노드인 “a”의 자식으로 추가한다. 3) “c”도 마찬가지로 “b”의 자식노드로 추가한다. 4) “abc”라는 단어가 여기서 끝남을 알리기 위해 현재 노드에 abc라고 표시한다.
✏ Step 2. ab 추가
1) Head의 자식 노드 “a”가 존재한다. 따라서 추가하지 않고 기존에 있던 “a”노드로 이동한다 2) “b”도 “a”의 자식노드로 이미 존재한다. “b”노드로 이동한다. 1) 여기서 “ab”라는 단어가 끝이 남으로, 현재 노드에 ab를 표시한다.
✏ Step 3. car 추가
1) Head의 자식 노드로 “c”는 존재하지 않는다. 따라서 “c”를 자식노드로 추가한다. 2) “c”의 하위노드가 없음으로 마찬가지로 “a”를 추가한다. “r”에 대해서도 동일하다. 3) “car”가 “r”노드에서 끝남으로 “car”를 표시해준다.
Python 구현
1. Node를 Class로 만들기
- Key :해당 노드의 문자
- Child : 자식 노드
- Data : 문자열이 끝나는 위치를 알려주는 역할 ex) “car”이 “r”에서 끝날 때, “r”을 key로 가지는 노드의 data에 “car”를 입력한다. 해당 노드에서 끝나는 문자열이 없을 경우에는 None으로 그대로 놔둔다.
class Node(object):
def __init__(self, key, data=None):
self.key = key
self.data = data
self.children = {}
2.Dictionary를 이용하여 Trie 기능을 구현한다.
class Trie(object):
def __init__(self):
self.head = Node(None)
def insert(self, string): # 문자열 삽입
curr_node = self.head
for char in string: # 삽입할 string 각각의 문자에 대해 자식 Node를 만들며 내려간다.
if char not in curr_node.children: # 자식 Node들 중 같은 문자가 없으면, Node 새로 생성
curr_node.children[char] = Node(char)
curr_node = curr_node.children[char] # 같은 문자가 있으면, 노드를 따로 생성하지 않고, 해당 노드로 이동
curr_node.data = string # 문자열이 끝난 지점의 노드의 data값에 해당 문자열을 입력
def search(self, string): # 문자열이 존재하는지 search
curr_node = self.head
for char in string:
if char in curr_node.children:
curr_node = curr_node.children[char]
else:
return False
if curr_node.data != None: #탐색이 끝난 후 해당 노드의 data값이 존재한다면, 문자가 포함되어있다는 뜻이다.
return True
Trie의 활용
Trie는 문자열의 Prefix를 판단하거나 탐색할때 매우 빠른 속도로 이용할 수 있다. 알고리즘 문제를 해결하기 위해서 사용되는 경우도 종종 있다.
예시 : 백준 5052번 [전화번호 목록], 백준 5670 [휴대폰 자판] 등
장점
앞에서도 언급했듯이 문자열을 빠르게 찾을 수 있다는 점이다. 또, 문자열을 집합에 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에 문자열의 추가와 탐색 모두 O(M)만에 가능하다.
단점
트라이가 자주 쓰이지 않는 이유는 필요한 메모리의 크기가 너무 크다는 단점 때문이다. 계속해서 노드를 만들어나가기 때문에 최악의 경우에는 집합 내 문자열들의 길이의 총합만큼 노드가 필요하므로 총 메모리는 O(포인터 크기 * 포인터 배열 개수 * 총노드의 개수)가 된다.
⇒ 따라서, 이 단점을 해결하기 위해서 보통 map이나 vector를 이용하여 필요한 노드만 메모리를 할당하는 방식들을 이용하는데, 문제에 따라서 메모리 제한이 빡빡한 경우에는 최적화가 꽤나 까다롭다.
⇒ 또한, 문제에서 주어진 조건을 보고 트라이를 이용할 수 있는 문제인지 파악하는 것도 중요하다.