[C++로 배우는 알고리즘과 자료구조 심화] Day 1: 트라이(Trie) 자료구조와 문자열 검색

트라이(Trie) 자료구조 소개

트라이(Trie)는 문자열 또는 단어의 집합을 저장하고 효율적으로 검색하기 위한 트리 기반의 자료구조입니다. 주로 문자열 검색, 자동 완성, 사전 구현 등에 사용됩니다. 트라이는 각 노드가 문자 하나를 나타내며, 루트 노드에서 시작하여 각 문자를 따라가면서 단어를 구성합니다.

트라이의 주요 특징

1. 빠른 검색: 문자열의 길이에 비례하는 시간 복잡도 (O(L))에서 검색이 가능합니다. 여기서 (L)은 문자열의 길이입니다.
2. 공유 구조: 공통 접두사를 가지는 문자열을 공유하여 공간을 절약합니다.
3. 삽입과 검색의 단순함: 삽입과 검색 연산이 단순하고 직관적입니다.

트라이의 기본 연산

1. 삽입 (Insert): 문자열을 트라이에 삽입합니다.
2. 검색 (Search): 문자열이 트라이에 존재하는지 확인합니다.
3. 삭제 (Delete): 문자열을 트라이에서 삭제합니다.

트라이의 구현

다음은 C++로 트라이를 구현한 예제입니다. 삽입과 검색 연산을 포함합니다.

 

트라이 노드 정의

#include <iostream>
#include <unordered_map>

// 트라이 노드 구조체 정의
struct TrieNode {
    bool isEndOfWord; // 단어의 끝을 나타내는 플래그
    std::unordered_map<char, TrieNode*> children; // 자식 노드를 저장하는 해시 맵

    TrieNode() : isEndOfWord(false) {}
};

 

트라이 클래스 정의

class Trie {
public:
    Trie();
    void insert(const std::string& word); // 단어 삽입 함수
    bool search(const std::string& word); // 단어 검색 함수

private:
    TrieNode* root; // 루트 노드
};

// 트라이 생성자 정의
Trie::Trie() {
    root = new TrieNode();
}

// 단어 삽입 함수 정의
void Trie::insert(const std::string& word) {
    TrieNode* currentNode = root;
    for (char ch : word) {
        if (currentNode->children.find(ch) == currentNode->children.end()) {
            currentNode->children[ch] = new TrieNode();
        }
        currentNode = currentNode->children[ch];
    }
    currentNode->isEndOfWord = true; // 단어의 끝을 표시
}

// 단어 검색 함수 정의
bool Trie::search(const std::string& word) {
    TrieNode* currentNode = root;
    for (char ch : word) {
        if (currentNode->children.find(ch) == currentNode->children.end()) {
            return false;
        }
        currentNode = currentNode->children[ch];
    }
    return currentNode->isEndOfWord;
}

 

사용 예제

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    trie.insert("bat");

    std::cout << "apple 검색: " << (trie.search("apple") ? "존재" : "존재하지 않음") << std::endl;
    std::cout << "app 검색: " << (trie.search("app") ? "존재" : "존재하지 않음") << std::endl;
    std::cout << "bat 검색: " << (trie.search("bat") ? "존재" : "존재하지 않음") << std::endl;
    std::cout << "batman 검색: " << (trie.search("batman") ? "존재" : "존재하지 않음") << std::endl;

    return 0;
}

 

설명

1. 트라이 노드 구조체:
   • isEndOfWord: 해당 노드가 단어의 끝인지 나타내는 불리언 값입니다.
   • children: 자식 노드를 저장하는 해시 맵입니다.
2. 트라이 클래스:
   • insert: 문자열을 트라이에 삽입하는 함수입니다. 각 문자를 따라가면서 새로운 노드를 추가합니다.
   • search: 문자열이 트라이에 존재하는지 확인하는 함수입니다. 각 문자를 따라가면서 존재 여부를 확인합니다.

이론적인 부분과 코드 예제를 통해 트라이 자료구조의 기본 개념과 구현 방법을 이해했습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 2: 세그먼트 트리"에 대해 학습하겠습니다.