트라이(Trie)는 문자열을 저장하고 검색하는 효율적인 자료구조입니다. 트라이는 트리 형태로 구성되어 있으며, 각 노드는 문자를 나타내는 키와 자식 노드로 구성됩니다. 이 자료구조는 주로 문자열 검색, 자동 완성, 철자 교정 등에서 사용됩니다.
트라이의 구현
파이썬에서 트라이를 구현하려면 먼저 노드 클래스(Node class)를 정의해야 합니다. 각 노드는 현재 문자를 저장하는 value 변수와 자식 노드들을 저장하는 children 변수를 갖습니다. 또한, 각 노드의 마지막을 나타내는 flag 변수가 필요합니다.
class Node:
def __init__(self, value):
self.value = value
self.children = {}
self.flag = False
트라이 구조체는 루트 노드를 가리키는 root 변수를 갖습니다. 루트 노드는 비어 있는 문자를 저장하고, 자식 노드로 이어집니다.
class Trie:
def __init__(self):
self.root = Node('')
Trie 클래스에는 다음과 같은 기능을 구현할 수 있습니다:
- 문자열 삽입(insert): 주어진 문자열을 트라이에 삽입합니다.
- 문자열 검색(search): 주어진 문자열이 트라이에 존재하는지 확인합니다.
- 문자열 삭제(delete): 주어진 문자열을 트라이에서 삭제합니다.
트라이 활용 예시
트라이의 가장 일반적인 사용 사례 중 하나가 자동 완성입니다. 예를 들어, 사용자가 단어를 입력할 때마다 트라이를 사용하여 입력된 단어와 일치하는 모든 단어를 자동으로 완성할 수 있습니다.
아래는 트라이를 활용하여 자동 완성 기능을 구현하는 예시 코드입니다.
class Trie:
def __init__(self):
self.root = Node('')
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = Node(char)
node = node.children[char]
node.flag = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.flag
def autocomplete(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return []
node = node.children[char]
return self._dfs(node, prefix)
def _dfs(self, node, prefix):
result = []
if node.flag:
result.append(prefix)
for char, child in node.children.items():
result.extend(self._dfs(child, prefix + char))
return result
위의 코드에서 insert() 함수는 주어진 단어를 트라이에 삽입합니다. search() 함수는 주어진 단어가 트라이에 있는지 확인하고, autocomplete() 함수는 주어진 접두사(prefix)와 일치하는 모든 단어를 반환합니다.
이제 트라이를 활용하여 자동 완성 기능을 사용해보겠습니다.
trie = Trie()
trie.insert("apple")
trie.insert("banana")
trie.insert("orange")
trie.insert("pear")
print(trie.autocomplete("ap")) # ["apple"]
print(trie.autocomplete("ban")) # ["banana"]
print(trie.autocomplete("o")) # ["orange"]
print(trie.autocomplete("pea")) # ["pear"]
위의 출력은 각각 “ap”, “ban”, “o”, “pea” 접두사에 대해 해당하는 단어를 자동 완성한 결과를 보여줍니다.
트라이는 단어 검색 외에도 여러분의 상황에 맞게 활용할 수 있습니다. 기본적인 트라이 구현과 기능을 확장하여 다양한 응용 프로그램에 적용해보세요!