자바스크립트 코딩테스트 강좌, 트라이

본 강좌에서는 자바스크립트를 이용한 알고리즘 문제풀이와 트라이(Trie) 자료구조의 사용법에 대해 자세히 살펴보겠습니다. 트라이는 문자열 처리의 효율성을 높이는 데 매우 유용한 자료구조입니다. 이 강좌에서는 트라이를 활용하여 특정 문제를 해결하는 과정을 설명할 것입니다.

트라이(Trie)란?

트라이는 다수의 문자열을 저장하기 위해 사용하는 트리 형태의 자료구조입니다. 자주 사용되는 애플리케이션으로는 자동 완성, 단어 검색, 그리고 prefix 검색 등이 있습니다. 트라이의 각 노드는 문자열의 문자에 해당하며, 경로를 통해 단어를 효율적으로 구성할 수 있습니다.

문제: 단어 검색

다음은 트라이 자료구조를 활용한 문제입니다.

주어진 단어 리스트와 검색어를 입력받았을 때, 검색어가 리스트에 존재하는 모든 단어를 찾고, 검색어가 포함된 모든 단어를 반환하시오.

문제 해결 전략

우선, 트라이 구조를 구현합니다.
주어진 단어 리스트를 트라이에 삽입합니다.
검색어를 사용하여 트라이에서 가능한 모든 단어를 탐색합니다.

트라이 구현

트라이를 구현하기 위해서는 다음과 같은 기본 구조가 필요합니다:

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    search(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) return [];
            node = node.children[char];
        }
        return this._findAllWords(node, prefix);
    }

    _findAllWords(node, prefix) {
        const results = [];
        if (node.isEndOfWord) {
            results.push(prefix);
        }
        for (let char in node.children) {
            results.push(...this._findAllWords(node.children[char], prefix + char));
        }
        return results;
    }
}

단어 삽입 및 검색

이제 트라이에 단어를 삽입하고, 특정 검색어에 대해 가능한 모든 단어를 찾는 방법을 설명하겠습니다. 아래의 예시를 통해 과정을 보여줍니다:

const getWords = (words, searchWord) => {
    const trie = new Trie();
    for (let word of words) {
        trie.insert(word);
    }
    return trie.search(searchWord);
};

const wordsList = ["apple", "app", "apricot", "banana", "bat", "ball"];
const searchTerm = "ap";
const foundWords = getWords(wordsList, searchTerm);
console.log(foundWords); // ["apple", "app", "apricot"]

코드 설명

위의 코드에서 getWords 함수는 먼저 입력받은 단어 리스트를 트라이에 삽입한 후, 주어진 검색어로 트라이를 검색합니다. insert 메서드는 단어를 입력 받아 각 문자를 노드로 만들어 연결하며, search 메서드는 주어진 접두어에 해당하는 모든 단어를 찾아 반환합니다.

복잡도 분석

트라이의 삽입 및 검색 성능은 문자열의 길이와 트리의 깊이에 따라 달라집니다:

삽입: O(L), 여기서 L은 단어의 길이입니다.
검색: O(P + W), 여기서 P는 접두어의 길이, W는 결과로 반환되는 단어의 수입니다.

결론

이번 강좌에서는 자바스크립트에서 트라이 자료구조를 사용하여 문자열 검색 문제를 해결하는 방법을 알아보았습니다. 트라이는 대량의 단어를 효율적으로 처리할 수 있는 능력을 가지고 있어, 특히 자동완성 기능이나 단어 검색 기능을 구현할 때 매우 유용합니다.

트라이 알고리즘에 대해 더 많은 예제와 문제를 탐구하면서 자신의 이해도를 높여보세요. 다음 강좌에서도 더 많은 알고리즘과 자료구조에 대해 다룰 예정이니 많은 관심 부탁드립니다!