1. 서론
오늘의 강좌에서는 C++ 프로그래밍 언어를 사용하여 트라이(Trie) 자료구조에 대해 심도 있게 살펴보고,
이를 활용한 알고리즘 문제를 해결하겠습니다. 트라이는 문자열을 저장하고 검색하는 데 최적화된
자료구조로, 사전 찾기, 오토 컴플리션, 접두어 검색 등 다양한 문제를 해결하는 데 유용합니다.
2. 트라이 자료구조 소개
트라이는 각 노드가 문자열의 문자를 저장하며, 노드 간의 경로는 특정 문자열의 접두어를 나타냅니다.
이 자료구조를 사용하면 문자열 검색을 효율적으로 수행할 수 있는데, 기본 시간 복잡도는 O(m)입니다.
여기서 m은 검색하고자 하는 문자열의 길이입니다.
2.1 트라이의 구성
트라이의 기본 구성 요소는 다음과 같습니다:
- Node: 각 노드는 문자와 하위 노드를 포함합니다.
- Insert: 새로운 문자열을 트라이에 추가합니다.
- Search: 특정 문자열을 트라이에서 검색합니다.
- Delete: 특정 문자열을 트라이에서 삭제합니다.
2.2 트라이의 장점과 단점
트라이의 장점은 prefix(접두어) 검색이 용이하다는 것입니다. 그러나 메모리 사용량이 많고,
구현이 복잡할 수 있다는 단점이 있습니다.
3. 문제 정의
다음은 알고리즘 문제입니다.
주어진 문자열 리스트에서 특정 접두어를 가진 모든 단어를 출력하는 프로그램을 작성하세요.
문제 설명
입력:
– 단어 리스트 words: [“apple”, “app”, “application”, “bat”, “ban”, “band”]
– 특정 접두어 prefix: “ap”
출력:
– 접두어가 “ap”인 문자열: [“apple”, “app”, “application”]
4. 문제 해결 과정
4.1 트라이 클래스 정의
먼저, 트라이 노드를 정의하고, 트라이 클래스를 구현해야 합니다. 아래는 C++에서의 기본 구현입니다.
#include
#include
#include
#include
using namespace std;
class TrieNode {
public:
unordered_map children;
bool isEndOfWord;
TrieNode() : isEndOfWord(false) {}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children[c]) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->isEndOfWord = true;
}
void searchByPrefix(const string& prefix, vector& result, string current, TrieNode* node) {
if (node->isEndOfWord) {
result.push_back(current);
}
for (const auto& pair : node->children) {
searchByPrefix(prefix, result, current + pair.first, pair.second);
}
}
vector getWordsWithPrefix(const string& prefix) {
TrieNode* node = root;
vector result;
for (char c : prefix) {
if (!node->children[c]) {
return result; // No words with the given prefix
}
node = node->children[c];
}
searchByPrefix(prefix, result, prefix, node);
return result;
}
};
4.2 메인 함수 구현
이제 메인 함수를 구현하여 트라이에 단어를 삽입하고, 접두어로 단어를 검색해보겠습니다.
int main() {
Trie trie;
vector words = {"apple", "app", "application", "bat", "ban", "band"};
// Insert words into the trie
for (const string& word : words) {
trie.insert(word);
}
// Prefix to search
string prefix = "ap";
vector result = trie.getWordsWithPrefix(prefix);
// Print the result
cout << "Words with prefix '" << prefix << "': ";
for (const string& word : result) {
cout << word << " ";
}
cout << endl;
return 0;
}
5. 코드 실행 결과
위의 코드가 실행되면, 아래와 같은 결과가 출력됩니다.
주어진 접두어 “ap”에 해당하는 모든 단어가 리스트로 출력됩니다.
Words with prefix 'ap': apple app application
6. 결론
이번 강좌에서는 C++를 사용하여 트라이 데이터 구조를 구현하고, 특정 접두어를 가진 단어들을
검색하는 문제를 해결했습니다. 트라이는 문자열 관련 알고리즘 문제를 해결하는 데 매우 유용한
자료구조이며, 다양한 응용 분야에서 사용될 수 있습니다. 앞으로의 강좌에서도
다양한 알고리즘 문제 해결을 위해 레퍼런스로 사용할 수 있는 자료구조와 기법을 학습해 나가길
바랍니다. 감사합니다.