트라이(Trie) 알고리즘에 관하여

트라이는 문자열을 효율적으로 저장하고 탐색하기 위한 트리 자료구조로, 특히 접두사를 공유하는 문자열 집합에서 강력한 성능을 발휘합니다.

---

 

1. 트라이의 개념과 구조

트라이(Trie)는 트리 형태의 자료구조로, 문자열의 각 문자를 노드로 저장하여 문자열을 효율적으로 탐색할 수 있도록 구성됩니다. 트라이의 각 노드는 문자의 존재 여부를 나타내며 자식 노드를 통해 문자열이 이어집니다.

• 장점: 빠른 문자열 탐색, 자동완성 기능 지원
• 단점: 공간 복잡도가 상대적으로 높음

---

2. 트라이 알고리즘의 동작 원리

트라이 알고리즘은 크게 세 가지 연산으로 이루어집니다.

문자열 삽입 (insert)

문자열을 노드 단위로 삽입하며, 마지막 문자 노드에 문자열의 끝을 표시합니다.

문자열 검색 (search)

트리를 순회하며 문자열이 존재하는지 확인합니다. 마지막 문자 노드에 끝 표시가 있어야 문자열이 존재하는 것으로 간주합니다.

접두사 존재 여부 확인 (startsWith)

트리를 순회하여 접두사로 시작하는 문자열이 존재하는지를 확인합니다.

---

3. 트라이의 시간 복잡도와 공간 복잡도

• 시간 복잡도:
  • 삽입(insert): O(m), m은 문자열의 길이
  • 검색(search): O(m)
  • 접두사 탐색(startsWith): O(m)
• 공간 복잡도: O(n * m), n은 저장된 문자열의 개수, m은 문자열의 평균 길이

---

4. 트라이 구현

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26];
        isEndOfWord = false;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("apple");
        System.out.println(trie.search("apple"));   // true
        System.out.println(trie.search("app"));     // false
        System.out.println(trie.startsWith("app")); // true

        trie.insert("app");
        System.out.println(trie.search("app"));     // true
    }
}

---

4. 마무리

트라이 알고리즘은 문자열 탐색을 빠르게 처리할 수 있는 효율적인 자료구조로 다양한 분야에서 활용됩니다. 특히 많은 양의 데이터를 빠르게 검색하거나 자동완성 기능을 제공할 때 매우 효과적입니다. 다만 공간 복잡도가 높아 사용 환경에 따라 신중하게 선택하여 활용하는 것이 중요합니다.