1. 서론
안녕하세요! 오늘은 취업 준비생들에게 매우 유용한 트라이(Trie) 자료구조에 대해 알아보겠습니다. 여러 알고리즘 문제를 해결하기 위해서는 다양한 자료구조를 이해하고 활용할 수 있어야 하는데, 그 중 트라이 자료구조는 문자열 관련 문제를 효과적으로 해결하는 데 매우 강력합니다. 이번 포스트에서는 트라이의 개념, 특성, 활용 예시, 그리고 이를 통해 해결할 수 있는 문제를 다뤄보겠습니다.
2. 트라이(Trie) 자료구조란?
트라이는 다수의 문자열을 저장하는 데 최적화된 트리 구조입니다. 주로 문자열의 접두사(Prefix) 검색에 사용됩니다. 각 노드는 일반적으로 문자열의 문자 하나를 나타내며, 루트 노드에서 시작하여 자식 노드로 진행함으로써 문자열의 각 문자를 단계적으로 해석할 수 있습니다. 트라이는 다음과 같은 특징을 가지고 있습니다.
- 트라이의 각 노드는 문자와 해당 문자의 자식 노드를 가집니다.
- 속한 노드의 경로를 통해 문자열을 구성합니다.
- 중복된 문자열은 하나의 경로로 통합됩니다.
- 각 노드에서 종료 노드를 표시하여 문자열의 끝을 나타낼 수 있습니다.
3. 트라이 구조
트라이 구조는 다음과 같이 설계될 수 있습니다. 각 노드는 한 글자에 해당하며, 루트 노드부터 아래로 내려가며 문자열을 형성합니다. 예를 들어, 문자열 ‘cat’, ‘car’를 추가하면 다음과 같은 구조가 형성됩니다:
Root
└── c
├── a
│ ├── t (종료 노드)
│ └── r (종료 노드)
위의 구조를 통해 ‘ca’ 접두사를 가지는 문자열을 쉽게 탐색할 수 있습니다.
4. 트라이 구현하기
트라이를 구현하기 위해 먼저 클래스와 메소드를 정의해 보겠습니다. 기본적인 구현은 노드를 정의하고, 삽입, 검색, 삭제의 기능을 갖춘 트라이 클래스를 만드는 것입니다.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
위의 코드는 트라이 노드를 나타내는 TrieNode 클래스와, 기본적인 트라이 기능을 포함한 Trie 클래스를 정의합니다.
5. 문제: 문자열 목록에서 접두사를 찾기
이번에는 트라이를 활용하여 ‘접두사 검색’ 문제를 해결해 보겠습니다. 문제는 다음과 같습니다.
문제 설명
주어진 문자열의 목록이 있을 때, 특정 문자열이 이 목록의 어떤 문자열의 접두사인지 확인하는 프로그램을 작성하세요.
입력
- 문자열 목록: ["apple", "banana", "app", "apricot"] - 접두사: "app"
출력
'app'는 목록의 'apple'과 'app'의 접두사입니다.
이제 이 문제를 해결하기 위해 트라이를 활용해 보겠습니다.
6. 문제 해결 과정
트라이를 사용하여 이 문제를 해결해 보겠습니다. 먼저 문자열 목록을 트라이에 삽입한 후, 주어진 접두사가 트라이에 포함되어 있는지 확인합니다.
def find_prefix_words(words: List[str], prefix: str) -> List[str]:
trie = Trie()
for word in words:
trie.insert(word)
result = []
for word in words:
if word.startswith(prefix):
result.append(word)
return result
# 사용 예제
words = ["apple", "banana", "app", "apricot"]
prefix = "app"
print(find_prefix_words(words, prefix))
위의 코드는 문자열 목록을 입력받아, 해당 목록의 접두사를 찾는 기능을 구현한 것입니다. 사용자가 입력한 접두사로 시작하는 모든 문자열을 반환하도록 하였습니다.
7. 결론
트라이는 문자열 데이터 처리와 검색에서 큰 성능 향상을 가져야 합니다. 접두사 검색과 같은 문제를 해결하는 데 매우 강력한 도구입니다. 본 포스트에서 살펴본 것처럼, 트라이를 사용하면 문자 기반의 데이터를 효과적으로 다룰 수 있습니다. 오늘 포스트가 트라이 자료구조를 이해하는 데 도움이 되었길 바랍니다.
앞으로 더 많은 알고리즘 문제를 다루는 포스트를 기대해주세요!