트라이 (Trie)
이론
트라이(Trie)란 집합(set)에서 특정 키를 찾는 데 사용되는 m-ary 트리 자료구조 중 하나이다.
※ m-ary란 최대로 가질 수 있는 자식의 수를 말한다. m=2이면 이진트리이다.
주로 문자열을 빠르게 조회하기 위해 사용한다. 꼭 문자열에만 사용되는 것은 아니고, 비트와 같이 순서가 있는 열거 가능한 자료형에서도 사용할 수 있다.
출처 : 위키백과 - Trie
문자열을 예시로 들어보면 "nureongi"라는 문자열이 있을 때 루트노드부터 n -> u -> r -> ... -> i 까지 문자열 순서대로 각 알파벳이 자식 노드로 삽입된 형태로 구성되어있다.
장점
문자열 탐색에 드는 시간 복잡도가 O(n)으로 작다.
n개의 단어 사전에서 길이 m의 단어를 일일히 비교하며 찾기 위해서는 이진 검색 트리를 사용해도 O(mlogn)의 시간복잡도가 필요하다는 것을 생각하면 정말 빠르다는 것을 알 수 있다.
단점
공간복잡도가 크다.
만약 트라이 자료구조의 저장되는 문자열이 서로 겹치는 글자가 하나도 없는 최악의 경우, O(포인터 크기 * 포인터 개수 * 총 노드의 수) 만큼의 메모리가 필요하게 된다.
길이 1000의 문자열이 1000개만 들어와도 100만개의 노드가 필요하다.
문제에서 주어지는 문자열의 길이와 개수를 통해 트라이를 사용할 수 있는지 먼저 판단해야 한다.
트라이를 비트를 통해 최적화하는 방법이 있다고는 하는데, 아직 여기까지는 배우지 못했으므로 추후 정리하도록 하자.
활용
트라이는 문자열 탐색 문제, 자동 검색 완성 등에 주로 사용된다.
예를들어 'n'을 입력하면 사전에 n 다음에 나올 글자가 무엇인지 들어있으므로 이를 바탕으로 검색하려는 문자열이 존재하는지 확인할 수 있다.
구현
파이썬에서는 클래스를 통해 트라이 자료구조를 구현할 수 있다.
노드 클래스
class Node(object):
def __init__(self, key, has_end=False):
self.key = key #생략가능?
self.is_terminal = is_terminal
self.children = dict()먼저 각각의 노드 역할을 해줄 클래스를 정의해야 한다.
노드 클래스는 총 3개의 속성을 갖는다.
-
key : 해당 노드를 찾기 위한 key이다.
하지만 파이썬에서는 딕셔너리 구조를 이용해 그냥 key-value 형태로 값을 저장할 수 있기 때문에 꼭 필요하지 않을수도 있다.
key에 현재까지의 전체 문자열을 저장해 사용하는 등의 문제가 있을 수는 있지만, 꼭 필요하지 않다는 것을 알아두자. -
is_terminal : 해당 노드가 단어의 마지막임을 알려주는 bool 속성이다. "nureongi", "nur"이 동시에 저장되어있을 때 "nur"이 끝인 단어가 존재하는 것을 알려주는 역할을 한다. is_terminal 대신에 현재까지의 문자열을 저장하기도 한다.
-
children : 다음 글자로 어떤 것이 저장되어있는지 저장하는 속성이다. 부모-자식을 연결하는 핵심 속성이라 할 수 있다.
트라이
class Trie(object):
# 최초 생성 시 헤드 노드 생성
def __init__(self):
self.head = Node(None)
# 트라이에 문자열 삽입
def insert(self, string):
curr_node = self.head
for char in string:
# 현재 노드에 해당하는 글자의 자식이 없다면 추가
if curr_node.children.get(char) is None:
curr_node.children[char] = Node()
# 다음 노드로 이동
curr_node = curr_node.children[char]
# 반복 종료 후 단어의 끝 표시
curr_node.is_termianl = True
# 트라이에서 전화번호 조회
def search(self, string):
curr_node = self.head
for char in string:
# 찾아야하는 글자가 없다면 해당 단어가 트라이에 없음
if curr_node.children.get(char) is None:
return False
# 다음 노드로 이동
curr_node = curr_node.children[char]
# 탐색이 종료되었다면 단어가 있다는 것이므로 True 반환
return True예제
문제 : 5052. 전화번호 목록
전화번호를 문자열 처럼 저장하여 탐색하는 문제로 트라이를 연습하기 적절하다.
풀이
- 크게 두가지 방법으로 풀어보았다.
브루트포스
- 모든 전화번호를 트라이에 삽입
- 다시 모든 전화번호에 대해 트라이 search 진행 -> 일관성이 깨진 번호라면
is_terminal = True이면서children != {}인 노드가 있을 것이다. 이를 바탕으로 탐색하면 된다.
정렬 이용
- 전화번호를 길이가 짧은 순으로 정렬
- 정렬된 전화번호를 순차 탐색하며 먼저 일관성 유지 여부를 탐색한 뒤 전화번호 삽입
- 길이가 짧은 것이 트라이에 먼저 삽입 되기 때문에, 나중에 길이가 긴 전화번호를 탐색하는 과정에서 일관성이 깨지는지 여부를 확인할 수 있다. (길이가 긴 것이 먼저 삽입되면 검사 못함)
코드
둘 다 해본결과 정렬을 이용하는 방법이 더 빨랐다.
# 트라이 자료구조
import sys
input = sys.stdin.readline
class Node(object):
def __init__(self, has_end=False):
self.has_end = has_end
self.children = dict()
class Trie(object):
def __init__(self):
self.head = Node(None)
# 트라이에 전화번호 추가
def insert(self, num):
curr_node = self.head
for d in num:
# 현재 노드에 해당하는 숫자의 자식이 없으면 생성
if curr_node.children.get(d) is None:
curr_node.children[d] = Node()
# 해당하는 숫자 자식으로 이동
curr_node = curr_node.children[d]
# 자료구조 말단에서 끝 표시
curr_node.has_end = True
# 트라이에서 전화번호 조회
def search(self, num):
curr_node = self.head
for d in num:
# 해당하는 숫자의 자식이 없으면 전화 가능하므로 일관성 있음
if curr_node.children.get(d) is None:
return True
curr_node = curr_node.children[d]
# 현재 위치에서 끝나는 전화번호가 있다면 해당 번호로 전화되므로 일관성 없음
if curr_node.has_end:
return False
return True
if __name__=="__main__":
t = int(input())
for _ in range(t):
n = int(input())
phone_numbers = [input().rstrip() for _ in range(n)]
# 길이가 짧은 것 부터 삽입하기 위해 정렬
phone_numbers = list(map(lambda x : (len(x), x), phone_numbers))
phone_numbers.sort(key = lambda x : x[0])
data = Trie()
# 번호에 대해 일관성 있는지 확인후 Trie 자료구조 데이터에 삽입
for _, number in phone_numbers:
# 일관성 없으면 즉시 NO 출력후 다음 테스트케이스 탐색
if data.search(number) == False:
print("NO")
break
# 일관성 있으면 데이터 삽입
data.insert(number)
# 모든 전화번호가 일관성 있다면 YES 출력
else:
print("YES")