이미지 로딩 중...
AI Generated
2025. 11. 7. · 3 Views
트라이 자료구조 완벽 가이드
트라이(Trie)는 문자열 검색과 자동완성 기능을 효율적으로 구현할 수 있는 트리 기반 자료구조입니다. 노드 구조부터 실전 활용까지, 중급 개발자를 위한 완벽한 가이드를 제공합니다.
목차
1. 트라이_노드_구조
시작하며
여러분이 검색 엔진이나 자동완성 기능을 구현할 때 이런 고민을 해본 적 있나요? "수천 개의 단어 중에서 특정 접두사로 시작하는 모든 단어를 빠르게 찾으려면 어떻게 해야 할까?" 배열이나 해시맵으로는 O(n) 시간이 걸리고, 매번 모든 단어를 순회해야 하는 비효율이 발생합니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. 포털 사이트의 검색창, IDE의 코드 자동완성, 사전 앱의 단어 추천 등 수많은 곳에서 빠른 문자열 검색이 필요하기 때문입니다.
특히 사용자가 타이핑하는 동안 실시간으로 결과를 보여줘야 하는 경우, 성능은 더욱 중요해집니다. 바로 이럴 때 필요한 것이 트라이(Trie) 자료구조입니다.
트라이의 핵심은 노드 구조에 있습니다. 각 노드가 문자 하나를 담당하고, 자식 노드들을 통해 다음 문자로 연결되는 구조로, O(m) 시간 복잡도(m은 문자열 길이)로 검색이 가능합니다.
개요
간단히 말해서, 트라이 노드는 하나의 문자 지점을 나타내며, 자식 노드들의 맵과 단어 종료 여부를 저장하는 구조입니다. 왜 이 구조가 필요한지 실무 관점에서 설명하면, 문자열 검색 시 매번 전체 단어를 비교할 필요 없이 문자 단위로 탐색할 수 있기 때문입니다.
예를 들어, "apple", "app", "apply"가 저장된 경우, "app"까지는 경로를 공유하고 이후에만 분기되므로 메모리와 검색 시간을 모두 절약할 수 있습니다. 전통적인 방법과의 비교를 해보면, 배열에 단어들을 저장했다면 매번 선형 탐색(O(n))이 필요했지만, 트라이를 사용하면 문자열 길이에만 비례하는 O(m) 시간으로 검색할 수 있습니다.
해시맵도 O(1) 검색이 가능하지만 접두사 기반 검색에는 적합하지 않습니다. 트라이 노드의 핵심 특징은 세 가지입니다.
첫째, children 맵을 통해 다음 문자로의 연결을 관리합니다. 둘째, isEndOfWord 플래그로 현재 위치에서 단어가 끝나는지 표시합니다.
셋째, 부모 참조 없이도 하향식 탐색만으로 모든 연산이 가능합니다. 이러한 특징들이 중요한 이유는 구조가 단순하면서도 강력한 검색 기능을 제공하기 때문입니다.
코드 예제
// 트라이 노드 클래스 - 각 노드는 하나의 문자 지점을 나타냄
class TrieNode {
constructor() {
// 자식 노드들을 저장하는 맵 (문자 -> 노드)
this.children = new Map();
// 이 노드에서 단어가 끝나는지 표시
this.isEndOfWord = false;
// 선택사항: 이 위치를 지나는 단어 개수
this.wordCount = 0;
}
// 자식 노드가 있는지 확인
hasChild(char) {
return this.children.has(char);
}
// 자식 노드 가져오기
getChild(char) {
return this.children.get(char);
}
}
설명
이것이 하는 일: 트라이 노드는 문자열의 각 문자 위치를 나타내는 객체로, 다음 문자들로의 연결과 단어 종료 정보를 관리합니다. 코드를 단계별로 나누어 설명하면, 첫 번째 단계는 생성자에서 children 맵을 초기화하는 것입니다.
Map 자료구조를 사용하는 이유는 동적으로 자식 노드를 추가/제거할 수 있고, 특정 문자의 자식 노드를 O(1) 시간에 찾을 수 있기 때문입니다. 배열을 사용할 수도 있지만(알파벳 26개 인덱스), Map은 유니코드 문자도 지원하므로 더 범용적입니다.
두 번째 단계로, isEndOfWord 플래그가 초기화됩니다. 이 플래그가 중요한 이유는 "app"과 "apple"이 모두 저장된 경우를 구분하기 위함입니다.
"app"의 마지막 'p' 노드는 isEndOfWord가 true이고, "apple"로 가는 경로의 중간 지점이기도 합니다. 이렇게 하나의 노드가 여러 역할을 할 수 있어 메모리 효율이 높습니다.
세 번째 단계는 선택적 속성인 wordCount입니다. 이는 자동완성에서 인기도 기반 정렬이나, 특정 접두사를 가진 단어의 개수를 빠르게 계산할 때 유용합니다.
각 노드에 저장하면 매번 서브트리를 순회할 필요 없이 O(1)로 접근할 수 있습니다. 헬퍼 메서드들은 코드의 가독성을 높이는 역할을 합니다.
hasChild는 존재 여부만 확인하고, getChild는 실제 노드 객체를 반환합니다. 이렇게 분리하면 삽입 시에는 hasChild로 확인 후 없으면 생성하고, 검색 시에는 getChild로 바로 다음 노드로 이동할 수 있습니다.
여러분이 이 코드를 사용하면 확장 가능하고 유지보수하기 쉬운 트라이 구조를 만들 수 있습니다. 실무에서의 이점은 첫째, Map 기반이라 다국어 지원이 쉽고, 둘째, wordCount로 통계 기능을 추가할 수 있으며, 셋째, 명확한 인터페이스로 버그 발생 가능성이 줄어듭니다.
실전 팁
💡 children을 Map 대신 객체({})로 구현하면 메모리를 약간 절약할 수 있지만, 프로토타입 체인 이슈와 hasOwnProperty 체크가 필요하므로 Map이 더 안전합니다.
💡 대소문자를 구분하지 않으려면 삽입/검색 시 toLowerCase()를 적용하세요. 하지만 원본 단어도 저장하려면 isEndOfWord 대신 words 배열을 사용하는 것이 좋습니다.
💡 메모리 사용량이 중요하다면 자식이 없고 단어도 끝나지 않는 노드는 주기적으로 제거하는 garbage collection을 구현하세요.
💡 디버깅 시 각 노드에 depth나 char 속성을 추가하면 트리 구조를 시각화하기 쉽습니다. 프로덕션에서는 제거하세요.
💡 멀티스레드 환경에서는 children Map 접근 시 동기화가 필요합니다. 읽기가 많다면 copy-on-write 패턴을 고려하세요.
2. 단어_삽입_연산
시작하며
여러분이 사전 앱을 만들 때 이런 상황을 겪어본 적 있나요? 새로운 단어를 추가할 때마다 기존 단어들과 중복 체크를 하고, 정렬된 순서를 유지하려면 삽입 위치를 찾아야 하는 번거로움이 있습니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. 단어가 늘어날수록 삽입 성능이 저하되고, 특히 정렬을 유지하려면 O(n)의 시간 복잡도가 필요합니다.
데이터베이스에 저장하더라도 인덱싱 오버헤드가 있습니다. 바로 이럴 때 필요한 것이 트라이의 삽입 연산입니다.
문자 단위로 경로를 만들어가면서 O(m) 시간에 단어를 추가할 수 있고, 자동으로 접두사가 공유되어 메모리 효율도 높습니다.
개요
간단히 말해서, 트라이 삽입은 문자열의 각 문자를 순회하면서 해당 경로가 없으면 노드를 생성하고, 마지막 노드에 단어 종료 표시를 하는 과정입니다. 왜 이 연산이 필요한지 실무 관점에서 설명하면, 동적으로 단어를 추가하면서도 검색 성능을 유지할 수 있기 때문입니다.
예를 들어, 사용자가 입력한 새로운 검색어를 실시간으로 추가하거나, 외부 API에서 받은 키워드 목록을 빠르게 구축할 수 있습니다. 전통적인 방법과의 비교를 해보면, 배열에 삽입하려면 정렬 유지를 위해 O(n)이 필요했지만, 트라이는 단어 길이에만 비례하는 O(m) 시간으로 삽입할 수 있습니다.
BST도 O(log n)이지만 접두사 검색이 어렵습니다. 삽입 연산의 핵심 특징은 세 가지입니다.
첫째, 기존 경로를 최대한 재사용하여 메모리를 절약합니다. 둘째, 중복 단어도 자연스럽게 처리됩니다(이미 있으면 isEndOfWord만 true로).
셋째, 순서에 관계없이 동일한 구조가 만들어집니다. 이러한 특징들이 중요한 이유는 구현이 단순하면서도 안정적이기 때문입니다.
코드 예제
class Trie {
constructor() {
this.root = new TrieNode();
}
// 단어를 트라이에 삽입
insert(word) {
let currentNode = this.root;
// 각 문자를 순회하면서 경로 생성
for (let char of word) {
// 자식 노드가 없으면 새로 생성
if (!currentNode.hasChild(char)) {
currentNode.children.set(char, new TrieNode());
}
// 다음 노드로 이동
currentNode = currentNode.getChild(char);
currentNode.wordCount++; // 이 경로를 지나는 단어 수 증가
}
// 마지막 노드에 단어 종료 표시
currentNode.isEndOfWord = true;
}
}
설명
이것이 하는 일: 삽입 연산은 루트부터 시작하여 문자열의 각 문자에 해당하는 경로를 따라가며, 없는 경로는 생성하고, 마지막에 단어 종료 플래그를 설정합니다. 코드를 단계별로 나누어 설명하면, 첫 번째 단계는 currentNode를 루트로 초기화하는 것입니다.
루트 노드는 빈 문자열을 나타내며, 모든 단어의 시작점입니다. 루트는 문자를 담지 않고 순수하게 시작점 역할만 하므로 isEndOfWord는 항상 false입니다(빈 문자열을 저장하는 특수한 경우 제외).
두 번째 단계로, for 루프가 각 문자를 처리합니다. hasChild로 자식 노드 존재를 확인하는데, 이는 "apple"을 삽입할 때 이미 "app"이 있다면 'a', 'p', 'p' 경로를 재사용하고 'l', 'e'만 새로 생성하기 위함입니다.
이렇게 하면 공통 접두사는 한 번만 저장되어 메모리가 크게 절약됩니다. 예를 들어 "app", "apple", "apply" 세 단어는 "app"까지 경로를 공유합니다.
세 번째 단계는 wordCount 증가입니다. 이는 선택적이지만 매우 유용한데, 나중에 "ap"로 시작하는 단어가 몇 개인지 O(1)에 알 수 있습니다.
자동완성에서 "인기 순위" 기능을 구현할 때, 각 접두사별 단어 수를 미리 계산해두면 실시간 정렬이 가능합니다. 마지막 단계는 isEndOfWord를 true로 설정하는 것입니다.
이는 매우 중요한데, 예를 들어 "car"와 "card"가 모두 저장된 경우, 'r' 노드의 isEndOfWord가 true이고 'd' 노드의 isEndOfWord도 true입니다. 'r' 노드는 단어의 끝이면서 동시에 다른 단어의 중간 지점이 될 수 있습니다.
여러분이 이 코드를 사용하면 수십만 개의 단어를 빠르게 구축할 수 있습니다. 실무에서의 이점은 첫째, 단어 길이에만 비례하는 예측 가능한 성능, 둘째, 중복 처리가 자동으로 되어 별도 체크 불필요, 셋째, 메모리 효율적인 저장 구조입니다.
실전 팁
💡 대량의 단어를 삽입할 때는 긴 단어부터 삽입하면 캐시 지역성이 향상되어 약간 더 빠릅니다. 하지만 실제 차이는 미미하므로 순서는 크게 중요하지 않습니다.
💡 중복 단어 삽입 시 카운트를 세고 싶다면 isEndOfWord를 boolean 대신 count 숫자로 변경하세요. 검색어 인기도 측정에 유용합니다.
💡 삽입 실패 처리를 원한다면 빈 문자열이나 null 체크를 추가하세요. 프로덕션에서는 입력 검증이 필수입니다.
💡 성능 측정 시 삽입 시간뿐 아니라 메모리 사용량도 모니터링하세요. Node.js에서는 process.memoryUsage()로 확인 가능합니다.
💡 트랜잭션이 필요하다면 삽입 전 스냅샷을 저장하고, 실패 시 롤백하는 메커니즘을 구현하세요. 불변 자료구조 라이브러리(Immutable.js)를 고려할 수도 있습니다.
3. 단어_검색_연산
시작하며
여러분이 단어 검증 기능을 구현할 때 이런 고민을 해본 적 있나요? 사용자가 입력한 단어가 사전에 있는 정확한 단어인지 확인하려면 어떻게 해야 할까요?
배열을 순회하면 O(n) 시간이 걸리고, 이진 탐색을 쓰려면 정렬된 상태를 유지해야 합니다. 이런 문제는 실제 개발 현장에서 자주 발생합니다.
맞춤법 검사기, 게임의 단어 맞추기, 금칙어 필터링 등 정확한 단어 매칭이 필요한 곳은 수없이 많습니다. 특히 실시간으로 검증해야 할 때는 성능이 더욱 중요합니다.
바로 이럴 때 필요한 것이 트라이의 검색 연산입니다. 문자 단위로 경로를 따라가면서 O(m) 시간에 단어 존재 여부를 확인할 수 있고, 중간에 경로가 끊기면 즉시 false를 반환하여 불필요한 비교를 피할 수 있습니다.
개요
간단히 말해서, 트라이 검색은 문자열의 각 문자를 순회하면서 해당 경로가 존재하는지 확인하고, 마지막 노드의 isEndOfWord가 true인지 체크하는 과정입니다. 왜 이 연산이 필요한지 실무 관점에서 설명하면, 단순히 경로가 존재하는 것과 실제로 단어가 끝나는 것은 다르기 때문입니다.
예를 들어, "apple"이 저장된 상태에서 "app"을 검색하면 경로는 존재하지만 "app" 자체가 별도로 삽입되지 않았다면 false를 반환해야 합니다. 이는 접두사 검색과는 다른 완전 일치 검색입니다.
전통적인 방법과의 비교를 해보면, Set이나 HashMap은 O(1) 검색이 가능하지만 접두사 기반 확장이 어렵습니다. 트라이는 O(m)이지만 검색과 접두사 매칭을 동시에 지원하며, 같은 자료구조로 다양한 문자열 연산을 수행할 수 있습니다.
검색 연산의 핵심 특징은 세 가지입니다. 첫째, 조기 종료(early termination)로 불필요한 비교를 피합니다.
둘째, isEndOfWord 체크로 완전 일치만 인정합니다. 셋째, null 안전성을 위해 각 단계에서 노드 존재를 확인합니다.
이러한 특징들이 중요한 이유는 안정적이고 예측 가능한 검색 결과를 보장하기 때문입니다.
코드 예제
// Trie 클래스에 추가
search(word) {
let currentNode = this.root;
// 각 문자를 순회하면서 경로 확인
for (let char of word) {
// 자식 노드가 없으면 단어가 없음
if (!currentNode.hasChild(char)) {
return false;
}
// 다음 노드로 이동
currentNode = currentNode.getChild(char);
}
// 경로는 존재하지만 단어로 끝나는지 확인
// "app"이 없고 "apple"만 있을 때 "app" 검색 시 false 반환
return currentNode.isEndOfWord;
}
설명
이것이 하는 일: 검색 연산은 루트부터 시작하여 문자열의 각 문자에 해당하는 자식 노드로 이동하면서 경로의 존재를 확인하고, 최종적으로 단어 종료 플래그를 검사하여 완전 일치 여부를 판단합니다. 코드를 단계별로 나누어 설명하면, 첫 번째 단계는 currentNode를 루트로 초기화하는 것입니다.
이는 삽입과 동일한 시작점이며, 모든 문자열 연산의 공통 출발점입니다. 루트는 실제 문자를 담지 않으므로 첫 번째 문자부터 바로 자식 노드를 검색합니다.
두 번째 단계로, for 루프가 각 문자를 처리하는데, 여기서 핵심은 조기 종료입니다. hasChild가 false를 반환하면 즉시 false를 리턴하므로 나머지 문자를 확인할 필요가 없습니다.
예를 들어, "application"을 검색하는데 "app"까지만 있다면 'l'에서 바로 false가 반환되어 "lication"은 확인하지 않습니다. 이는 긴 단어일수록 성능 이점이 큽니다.
세 번째 단계는 getChild로 다음 노드로 이동하는 것입니다. 이미 hasChild에서 존재를 확인했으므로 getChild는 항상 유효한 노드를 반환합니다.
이렇게 확인과 접근을 분리하면 코드가 명확해지고, 나중에 로깅이나 통계를 추가하기도 쉽습니다. 마지막 단계는 isEndOfWord를 반환하는 것인데, 이는 매우 중요한 구분입니다.
예를 들어, "car", "card", "care"가 모두 저장된 상태에서 "car"를 검색하면 'r' 노드까지 도달하지만, "car"가 별도로 삽입되지 않았다면 'r' 노드의 isEndOfWord는 false입니다. 반대로 "car"도 삽입되었다면 'r' 노드는 단어의 끝이면서 동시에 "card", "care"의 중간 노드 역할을 합니다.
여러분이 이 코드를 사용하면 밀리초 단위의 빠른 검색으로 사용자 경험을 개선할 수 있습니다. 실무에서의 이점은 첫째, 단어 길이에만 비례하는 예측 가능한 성능, 둘째, 조기 종료로 평균 성능이 더 좋음, 셋째, 명확한 true/false 결과로 버그 가능성이 낮습니다.
실전 팁
💡 대소문자를 구분하지 않으려면 검색 전에 toLowerCase()를 적용하세요. 단, 삽입할 때도 동일하게 적용해야 합니다.
💡 검색 성능을 모니터링하려면 각 검색 시 방문한 노드 수를 카운트하세요. 이는 트라이 깊이와 분기 계수를 분석하는 데 유용합니다.
💡 부분 일치를 허용하려면 isEndOfWord 체크를 제거하면 되지만, 이는 접두사 검색과 동일하므로 별도 메서드로 분리하는 것이 좋습니다.
💡 검색 중 경로를 추적하려면 방문한 노드들을 배열에 저장하세요. 디버깅이나 "did you mean?" 기능 구현에 유용합니다.
💡 멀티스레드 환경에서는 검색 중 구조 변경을 방지하기 위해 읽기 락을 사용하거나, 불변 자료구조를 고려하세요.
4. 접두사_검색
시작하며
여러분이 검색창에서 자동완성 기능을 구현할 때 이런 상황을 겪어본 적 있나요? 사용자가 "app"만 입력했는데 "apple", "application", "apply" 등 수십 개의 관련 단어를 실시간으로 보여줘야 하는 상황입니다.
배열을 순회하면서 startsWith()를 호출하면 O(n*m) 시간이 걸려 사용자가 타이핑할 때마다 버벅입니다. 이런 문제는 실제 개발 현장에서 자주 발생합니다.
구글 검색창, VS Code의 IntelliSense, 쇼핑몰의 상품 검색 등 자동완성은 현대 UI의 필수 요소입니다. 특히 모바일에서는 타이핑이 불편하므로 정확한 자동완성이 더욱 중요합니다.
바로 이럴 때 필요한 것이 트라이의 접두사 검색입니다. 접두사까지 경로를 따라간 후, 그 아래 서브트리의 모든 단어를 수집하면 O(p+n) 시간(p는 접두사 길이, n은 결과 개수)에 모든 후보를 찾을 수 있습니다.
개요
간단히 말해서, 접두사 검색은 주어진 접두사까지 트라이를 탐색한 후, 그 노드를 루트로 하는 서브트리에서 모든 완성된 단어를 DFS나 BFS로 수집하는 과정입니다. 왜 이 연산이 필요한지 실무 관점에서 설명하면, 사용자가 타이핑하는 동안 즉시 피드백을 주어야 하기 때문입니다.
예를 들어, 이커머스 사이트에서 "삼성"을 입력하면 "삼성전자", "삼성갤럭시", "삼성노트북" 등을 즉시 보여줘서 클릭 한 번으로 원하는 상품을 찾게 할 수 있습니다. 이는 전환율 향상으로 직결됩니다.
전통적인 방법과의 비교를 해보면, 선형 탐색으로 모든 단어를 확인하면 O(n*m)이지만, 트라이는 접두사로 필터링된 서브트리만 탐색하므로 훨씬 효율적입니다. 특히 접두사가 길수록(사용자가 더 많이 타이핑할수록) 탐색 범위가 좁아져 성능이 향상됩니다.
접두사 검색의 핵심 특징은 세 가지입니다. 첫째, 접두사 검증과 단어 수집을 분리하여 코드가 명확합니다.
둘째, DFS를 사용하여 사전 순으로 결과를 얻을 수 있습니다. 셋째, wordCount를 활용하면 결과 개수를 미리 예측할 수 있습니다.
이러한 특징들이 중요한 이유는 유연하고 확장 가능한 자동완성을 구현할 수 있기 때문입니다.
코드 예제
// 접두사로 시작하는 모든 단어 찾기
startsWith(prefix) {
let currentNode = this.root;
// 접두사까지 경로 탐색
for (let char of prefix) {
if (!currentNode.hasChild(char)) {
return []; // 접두사가 없으면 빈 배열 반환
}
currentNode = currentNode.getChild(char);
}
// 해당 노드 아래의 모든 단어 수집
return this._collectWords(currentNode, prefix);
}
// 서브트리의 모든 단어를 DFS로 수집
_collectWords(node, prefix) {
const words = [];
// 현재 노드가 단어 끝이면 추가
if (node.isEndOfWord) {
words.push(prefix);
}
// 모든 자식 노드 재귀 탐색
for (let [char, childNode] of node.children) {
words.push(...this._collectWords(childNode, prefix + char));
}
return words;
}
설명
이것이 하는 일: 접두사 검색은 두 단계로 작동합니다. 먼저 접두사에 해당하는 노드까지 탐색하고, 그 다음 해당 노드를 루트로 하는 서브트리의 모든 단어를 깊이 우선 탐색으로 수집합니다.
코드를 단계별로 나누어 설명하면, 첫 번째 단계는 startsWith 메서드가 접두사 경로를 확인하는 것입니다. 이는 일반 검색과 동일하지만, 경로가 끊기면 빈 배열을 반환하여 "해당 접두사로 시작하는 단어가 없음"을 명확히 표현합니다.
예를 들어, "xyz"로 시작하는 단어가 하나도 없다면 첫 문자에서 바로 빈 배열이 반환됩니다. 두 번째 단계로, _collectWords 헬퍼 메서드가 호출됩니다.
prefix 매개변수를 함께 전달하는데, 이는 재귀 호출 시 현재까지 구성된 문자열을 추적하기 위함입니다. 예를 들어, "app"로 시작하는 단어를 찾을 때, 처음에는 prefix가 "app"이고, 'l' 자식을 탐색하면 "appl", 'e'를 탐색하면 "apple"이 됩니다.
세 번째 단계는 현재 노드가 단어의 끝인지 확인하는 것입니다. isEndOfWord가 true이면 현재 prefix를 결과 배열에 추가합니다.
이는 "app"을 검색할 때 "app" 자체도 단어이고 "apple"도 있는 경우, 둘 다 결과에 포함되도록 합니다. 네 번째 단계는 재귀적으로 모든 자식 노드를 탐색하는 것입니다.
for...of 루프가 children Map을 순회하는데, Map은 삽입 순서를 보장하지만 사전 순이 필요하면 정렬이 필요합니다. 각 자식에 대해 재귀 호출하고, spread 연산자(...)로 결과를 병합합니다.
이는 DFS 방식으로 깊이를 우선 탐색하여 메모리 사용이 효율적입니다. 여러분이 이 코드를 사용하면 실시간 자동완성으로 사용자 경험을 크게 개선할 수 있습니다.
실무에서의 이점은 첫째, 접두사가 길수록 검색 범위가 좁아져 성능이 향상되고, 둘째, 재귀 구조로 코드가 간결하며, 셋째, 결과를 즉시 스트리밍할 수 있어 응답성이 좋습니다.
실전 팁
💡 결과가 너무 많으면 재귀 깊이 제한이나 결과 개수 제한(limit)을 파라미터로 추가하세요. 자동완성은 보통 10개 이하만 표시합니다.
💡 사전 순 정렬이 필요하면 Array.from(node.children.keys()).sort()로 키를 정렬한 후 순회하세요. 또는 children을 Map 대신 정렬된 구조로 유지하세요.
💡 인기도 순 정렬을 원하면 각 단어에 빈도수를 저장하고, 수집 후 정렬하세요. 또는 우선순위 큐를 사용하여 Top-K만 유지할 수 있습니다.
💡 성능 최적화를 위해 자주 검색되는 접두사는 캐싱하세요. LRU 캐시를 사용하면 메모리 사용량을 제어할 수 있습니다.
💡 비동기 처리가 필요하면 재귀를 async/await로 변환하고, 일정 개수마다 yield하여 UI 블로킹을 방지하세요.
5. 단어_삭제_연산
시작하며
여러분이 단어 필터링 시스템을 운영할 때 이런 상황을 겪어본 적 있나요? 더 이상 필요하지 않은 단어를 삭제해야 하는데, 단순히 isEndOfWord를 false로 바꾸면 메모리에는 여전히 노드들이 남아 있어 점점 메모리 사용량이 증가합니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. 동적 금칙어 목록, 시즌별 검색어 관리, 사용자 커스텀 사전 등 단어를 추가/삭제가 빈번한 시스템에서는 메모리 누수가 심각한 문제가 될 수 있습니다.
바로 이럴 때 필요한 것이 트라이의 안전한 삭제 연산입니다. 단순히 표시만 지우는 것이 아니라, 더 이상 사용되지 않는 노드를 재귀적으로 제거하여 메모리를 확보하고, 다른 단어에 영향을 주지 않도록 신중하게 처리합니다.
개요
간단히 말해서, 트라이 삭제는 단어의 경로를 따라가면서 마지막 노드의 isEndOfWord를 false로 설정하고, 더 이상 자식이 없고 다른 단어의 일부도 아닌 노드들을 상향식으로 제거하는 과정입니다. 왜 이 연산이 필요한지 실무 관점에서 설명하면, 메모리 효율성과 정확성을 동시에 보장해야 하기 때문입니다.
예를 들어, "apple"을 삭제할 때 "app"도 저장되어 있다면 'p' 노드까지만 유지하고 'l', 'e' 노드는 제거해야 합니다. 잘못 삭제하면 "app"도 함께 사라지는 버그가 발생합니다.
전통적인 방법과의 비교를 해보면, 단순 배열이나 Set에서는 삭제가 O(1) 또는 O(n)이지만, 트라이는 O(m)으로 단어 길이에 비례하며 공유 구조를 신중히 처리해야 합니다. 하지만 한 번 올바르게 구현하면 안전하고 예측 가능한 동작을 보장합니다.
삭제 연산의 핵심 특징은 세 가지입니다. 첫째, 재귀적 삭제로 사용되지 않는 노드를 자동으로 정리합니다.
둘째, 다른 단어와 공유되는 노드는 보존합니다. 셋째, 존재하지 않는 단어 삭제 시도도 안전하게 처리합니다.
이러한 특징들이 중요한 이유는 복잡한 공유 구조에서도 버그 없이 동작하기 때문입니다.
코드 예제
// 단어를 트라이에서 삭제 (재귀 방식)
delete(word) {
return this._deleteRecursive(this.root, word, 0);
}
_deleteRecursive(node, word, index) {
// 베이스 케이스: 단어 끝에 도달
if (index === word.length) {
// 단어가 아니면 삭제 실패
if (!node.isEndOfWord) return false;
// 단어 표시 제거
node.isEndOfWord = false;
// 자식이 없으면 이 노드 삭제 가능
return node.children.size === 0;
}
const char = word[index];
const childNode = node.getChild(char);
// 경로가 없으면 삭제 실패
if (!childNode) return false;
// 재귀적으로 자식 처리
const shouldDeleteChild = this._deleteRecursive(childNode, word, index + 1);
// 자식을 삭제해야 하면 제거
if (shouldDeleteChild) {
node.children.delete(char);
// 현재 노드도 삭제 가능한지 확인 (다른 단어의 일부가 아닌지)
return !node.isEndOfWord && node.children.size === 0;
}
return false;
}
설명
이것이 하는 일: 삭제 연산은 재귀적으로 단어의 각 문자 경로를 따라가면서, 마지막 노드의 단어 표시를 제거하고, 되돌아오면서 더 이상 필요 없는 노드를 정리합니다. 코드를 단계별로 나누어 설명하면, 첫 번째 단계는 delete 메서드가 재귀 헬퍼 메서드를 호출하는 것입니다.
재귀를 사용하는 이유는 하향식으로 경로를 찾아간 후, 상향식으로 되돌아오면서 노드 삭제 여부를 결정해야 하기 때문입니다. index 매개변수는 현재 처리 중인 문자 위치를 추적합니다.
두 번째 단계로, 베이스 케이스가 단어 끝에 도달했는지 확인합니다. index === word.length이면 마지막 노드에 도착한 것인데, 여기서 isEndOfWord를 확인하여 실제로 단어가 존재하는지 검증합니다.
존재하지 않는 단어를 삭제하려 하면 false를 반환하여 실패를 알립니다. 존재한다면 isEndOfWord를 false로 설정하고, 자식이 없으면 true를 반환하여 "이 노드를 삭제해도 됨"을 부모에게 알립니다.
세 번째 단계는 재귀 호출로 자식 노드를 처리하는 것입니다. shouldDeleteChild 변수가 자식으로부터 받은 삭제 가능 여부를 저장합니다.
예를 들어, "apple"을 삭제할 때, 'e' 노드가 자식이 없고 단어도 아니면 true를 반환하고, 'l' 노드가 이를 받아 'e' 노드를 삭제합니다. 네 번째 단계는 조건부 삭제 결정입니다.
shouldDeleteChild가 true이면 children.delete(char)로 자식을 제거하는데, 이때 중요한 것은 현재 노드도 삭제 가능한지 확인하는 것입니다. 현재 노드가 다른 단어의 끝이거나(!node.isEndOfWord) 다른 자식이 있으면(node.children.size > 0) 삭제하면 안 됩니다.
예를 들어, "app"과 "apple"이 있을 때 "apple"을 삭제하면 'p' 노드는 "app"의 끝이므로 유지되어야 합니다. 여러분이 이 코드를 사용하면 메모리 누수 없이 동적으로 단어를 관리할 수 있습니다.
실무에서의 이점은 첫째, 자동으로 미사용 노드를 정리하여 메모리 효율이 높고, 둘째, 공유 구조를 안전하게 처리하여 버그가 없으며, 셋째, 재귀 구조로 코드가 명확하고 이해하기 쉽습니다.
실전 팁
💡 삭제 성공 여부를 반환하므로 사용자에게 "단어가 삭제되었습니다" 또는 "단어가 존재하지 않습니다" 피드백을 줄 수 있습니다.
💡 성능 최적화가 필요하면 wordCount를 활용하세요. 삭제 시 경로의 모든 노드에서 wordCount를 감소시키고, 0이 되면 서브트리 전체를 삭제할 수 있습니다.
💡 실수로 중요한 단어를 삭제하는 것을 방지하려면, 삭제 전 확인 콜백이나 "안전 단어" 목록을 구현하세요.
💡 대량 삭제 시 재귀 스택 오버플로우가 걱정된다면 반복문 기반 구현을 고려하세요. 스택 자료구조로 경로를 추적할 수 있습니다.
💡 삭제 이력을 유지하려면 소프트 삭제(isDeleted 플래그)를 고려하세요. 나중에 복구하거나 감사 로그를 남길 수 있습니다.
6. 와일드카드_검색
시작하며
여러분이 패턴 매칭 기능을 구현할 때 이런 상황을 겪어본 적 있나요? 사용자가 "a.ple"처럼 중간에 임의의 문자를 허용하는 검색을 하고 싶어 하는데, 정규식은 너무 무겁고 모든 단어를 순회하는 것은 비효율적입니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. 크로스워드 퍼즐 게임, 단어 맞추기 앱, 유연한 검색 기능 등 부분적인 정보만으로 단어를 찾아야 하는 경우가 많습니다.
특히 모바일 키보드의 오타를 감안한 검색이나 교육용 앱에서 유용합니다. 바로 이럴 때 필요한 것이 트라이의 와일드카드 검색입니다.
백트래킹을 활용하여 '.' 문자를 만나면 모든 가능한 자식을 탐색하고, 일반 문자는 정확히 매칭하여 효율적으로 패턴과 일치하는 모든 단어를 찾을 수 있습니다.
개요
간단히 말해서, 와일드카드 검색은 패턴 문자열에서 '.' 문자를 "임의의 한 문자"로 해석하고, DFS와 백트래킹을 사용하여 가능한 모든 경로를 탐색하는 과정입니다. 왜 이 연산이 필요한지 실무 관점에서 설명하면, 사용자가 단어의 일부만 기억하거나 오타가 있을 때도 결과를 제공할 수 있기 때문입니다.
예를 들어, "b.d"로 검색하면 "bad", "bed", "bid", "bud" 등을 모두 찾을 수 있어, 사용자가 정확히 기억하지 못해도 원하는 단어를 찾을 수 있습니다. 전통적인 방법과의 비교를 해보면, 정규식은 모든 단어에 대해 매칭을 시도하므로 O(n*m)이지만, 트라이는 불가능한 경로를 조기에 제외하여 평균적으로 훨씬 빠릅니다.
특히 와일드카드가 적을수록 성능 이점이 큽니다. 와일드카드 검색의 핵심 특징은 세 가지입니다.
첫째, 재귀와 백트래킹으로 모든 가능성을 탐색합니다. 둘째, 일반 문자는 정확히 매칭하여 탐색 범위를 줄입니다.
셋째, '.'를 만나면 모든 자식을 시도하여 유연성을 제공합니다. 이러한 특징들이 중요한 이유는 정확성과 성능의 균형을 맞출 수 있기 때문입니다.
코드 예제
// 와일드카드 검색 ('.'은 임의의 한 문자)
searchWithWildcard(pattern) {
return this._wildcardSearch(this.root, pattern, 0);
}
_wildcardSearch(node, pattern, index) {
// 베이스 케이스: 패턴 끝에 도달
if (index === pattern.length) {
return node.isEndOfWord;
}
const char = pattern[index];
// 와일드카드 문자인 경우
if (char === '.') {
// 모든 자식 노드를 시도 (백트래킹)
for (let [_, childNode] of node.children) {
if (this._wildcardSearch(childNode, pattern, index + 1)) {
return true; // 하나라도 매칭되면 성공
}
}
return false; // 모든 시도 실패
}
// 일반 문자인 경우 - 정확히 매칭
const childNode = node.getChild(char);
if (!childNode) return false;
return this._wildcardSearch(childNode, pattern, index + 1);
}
설명
이것이 하는 일: 와일드카드 검색은 패턴 문자열을 한 문자씩 처리하면서, 일반 문자는 정확한 경로를 따라가고, '.' 와일드카드는 해당 위치의 모든 가능한 자식 노드를 재귀적으로 탐색합니다. 코드를 단계별로 나누어 설명하면, 첫 번째 단계는 베이스 케이스 확인입니다.
index === pattern.length이면 패턴의 모든 문자를 처리한 것이므로, 현재 노드가 단어의 끝인지 확인합니다. 이는 일반 검색과 동일하게 isEndOfWord를 반환하여 완전 일치만 인정합니다.
두 번째 단계로, 현재 문자가 와일드카드('.')인지 확인합니다. 이 경우가 핵심인데, 모든 자식 노드를 순회하면서 각각에 대해 재귀 호출을 시도합니다.
예를 들어, "b.d" 패턴에서 'b' 다음 노드의 자식이 'a', 'e', 'i'라면, 각각 "bad", "bed", "bid"로 이어지는 경로를 모두 시도합니다. 하나라도 true를 반환하면 즉시 true를 반환하여 불필요한 탐색을 중단합니다.
세 번째 단계는 일반 문자 처리입니다. '.'가 아니면 정확히 해당 문자의 자식 노드만 찾습니다.
자식이 없으면 즉시 false를 반환하여 이 경로는 불가능함을 알립니다. 예를 들어, "b.d"에서 첫 번째 'b'를 처리할 때 'b' 자식이 없으면 나머지를 확인할 필요 없이 false입니다.
네 번째 단계는 백트래킹 메커니즘입니다. for 루프가 모든 자식을 시도하는데, 각 시도는 독립적입니다.
한 경로가 실패해도 다른 경로를 계속 시도하므로, 모든 가능성을 빠짐없이 확인합니다. 이는 깊이 우선 탐색의 특성으로, 한 경로를 끝까지 탐색한 후 다른 경로로 되돌아옵니다.
여러분이 이 코드를 사용하면 유연한 검색 기능으로 사용자 만족도를 높일 수 있습니다. 실무에서의 이점은 첫째, 부분적인 정보만으로도 검색 가능하고, 둘째, 트라이 구조로 불가능한 경로를 조기에 제외하며, 셋째, 확장하여 다른 와일드카드('*', '?')도 추가할 수 있습니다.
실전 팁
💡 모든 매칭 단어를 찾으려면 boolean 대신 배열을 반환하도록 수정하세요. true 반환 시 현재 경로를 배열에 추가하고 계속 탐색합니다.
💡 성능 최적화를 위해 와일드카드 위치를 분석하여, 앞쪽에 고정 문자가 많으면 해당 경로를 먼저 확정하세요.
💡 '*'(0개 이상의 문자) 와일드카드를 추가하려면, 현재 노드에서 자신과 모든 후손을 재귀적으로 시도하는 로직이 필요합니다.
💡 와일드카드가 많으면 탐색 공간이 기하급수적으로 증가하므로, 최대 깊이나 시간 제한을 설정하세요.
💡 대소문자 무시 와일드카드(예: '[a-z]')를 구현하려면, 해당 범위의 모든 문자를 시도하는 로직을 추가하세요.
7. 트라이_최적화
시작하며
여러분이 트라이를 실제 프로덕션에 적용할 때 이런 고민을 해본 적 있나요? 수십만 개의 단어를 저장하니 메모리 사용량이 수백 MB에 달하고, 서버의 RAM을 너무 많이 차지하는 문제가 발생합니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. 트라이는 검색 속도는 빠르지만 각 노드가 Map 객체를 가지므로 메모리 오버헤드가 큽니다.
특히 분기 계수가 낮은(자식이 적은) 노드가 많으면 메모리 낭비가 심합니다. 바로 이럴 때 필요한 것이 트라이 최적화 기법입니다.
압축 트라이(Radix Tree)로 변환하거나, 배열 기반 구조로 바꾸거나, 직렬화하여 디스크에 저장하는 등 다양한 방법으로 메모리를 크게 절약할 수 있습니다.
개요
간단히 말해서, 트라이 최적화는 메모리 사용량을 줄이고 캐시 효율을 높이기 위해 자식이 하나뿐인 노드 체인을 압축하거나, 자료구조를 변경하거나, 접근 패턴을 개선하는 기법들입니다. 왜 이 기법들이 필요한지 실무 관점에서 설명하면, 메모리는 유한한 자원이고 비용이 들기 때문입니다.
예를 들어, AWS EC2에서 메모리가 부족하면 더 큰 인스턴스로 업그레이드해야 하는데, 이는 월 비용이 2배 이상 증가할 수 있습니다. 최적화로 메모리를 절반으로 줄이면 서버 비용도 절감됩니다.
전통적인 방법과의 비교를 해보면, 기본 트라이는 구현이 단순하지만 메모리 오버헤드가 크고, 압축 트라이(Radix Tree)는 메모리를 30-50% 절약하지만 구현이 복잡합니다. 사용 사례에 따라 적절한 균형점을 찾아야 합니다.
최적화 기법의 핵심 특징은 세 가지입니다. 첫째, 경로 압축으로 자식이 하나뿐인 노드 체인을 문자열로 통합합니다.
둘째, 배열 기반 구조로 Map 오버헤드를 제거합니다. 셋째, 직렬화로 사용하지 않는 서브트리를 디스크로 스왑합니다.
이러한 특징들이 중요한 이유는 실제 대규모 시스템에서 트라이를 사용 가능하게 만들기 때문입니다.
코드 예제
// 압축 트라이 노드 (Radix Tree)
class CompressedTrieNode {
constructor() {
this.children = new Map();
this.isEndOfWord = false;
// 압축된 문자열 (자식이 하나뿐인 경로)
this.edge = '';
}
}
class CompressedTrie {
constructor() {
this.root = new CompressedTrieNode();
}
// 삽입 시 경로 압축
insert(word) {
let node = this.root;
let i = 0;
while (i < word.length) {
const char = word[i];
if (!node.children.has(char)) {
// 남은 부분을 압축하여 저장
const newNode = new CompressedTrieNode();
newNode.edge = word.slice(i);
newNode.isEndOfWord = true;
node.children.set(char, newNode);
return;
}
const child = node.children.get(char);
const edge = child.edge;
// 공통 접두사 찾기
let j = 0;
while (j < edge.length && i + j < word.length &&
edge[j] === word[i + j]) {
j++;
}
// 완전히 매칭되면 다음 노드로
if (j === edge.length) {
node = child;
i += j;
} else {
// 분기 필요: 노드 분할
this._splitNode(node, char, child, j, word.slice(i + j));
return;
}
}
node.isEndOfWord = true;
}
_splitNode(parent, char, child, splitPos, remainder) {
// 구현 복잡도로 인해 생략 (실무에서는 신중히 구현)
// 기존 노드를 분할하여 새 중간 노드 생성
}
}
설명
이것이 하는 일: 압축 트라이는 기본 트라이의 메모리 낭비를 줄이기 위해, 분기가 없는 경로를 하나의 노드로 통합하여 노드 개수를 최소화합니다. 코드를 단계별로 나누어 설명하면, 첫 번째 단계는 CompressedTrieNode에 edge 속성을 추가하는 것입니다.
이는 현재 노드에서 다음 분기까지의 문자열을 저장합니다. 예를 들어, "apple"만 저장된 경우, 루트의 자식 하나가 edge="apple"을 가지며, 5개 노드 대신 2개 노드로 표현됩니다.
두 번째 단계로, 삽입 시 기존 edge와의 공통 접두사를 찾습니다. while 루프가 문자를 하나씩 비교하여 어디까지 일치하는지 확인하는데, 이는 새 단어가 기존 경로와 어느 지점에서 분기되는지 찾기 위함입니다.
예를 들어, "apple"이 있을 때 "apply"를 삽입하면 "appl"까지 공통이므로 'y'에서 분기됩니다. 세 번째 단계는 완전 매칭 케이스입니다.
j === edge.length이면 현재 edge를 완전히 소비한 것이므로 자식 노드로 이동하여 계속 처리합니다. 이는 기본 트라이의 다음 노드 이동과 동일하지만, 한 번에 여러 문자를 건너뛸 수 있어 효율적입니다.
네 번째 단계는 노드 분할로, 가장 복잡한 부분입니다. 부분적으로만 매칭되면 기존 노드를 쪼개야 하는데, 예를 들어 edge="pple"인 노드에 "pply"를 추가하려면, 새 노드를 만들어 edge="ppl"로 설정하고, 두 자식에 각각 "e"와 "y"를 연결해야 합니다.
이는 트리 구조를 재구성하므로 주의가 필요합니다. 여러분이 이 코드를 사용하면 메모리 사용량을 30-70% 절약할 수 있습니다.
실무에서의 이점은 첫째, 긴 단어일수록 압축 효과가 크고, 둘째, 검색 성능은 거의 동일하며, 셋째, 메모리 제약이 있는 임베디드 시스템이나 모바일 앱에 적합합니다. 단점은 구현이 복잡하고 삽입/삭제 시 노드 분할/병합 로직이 필요하다는 것입니다.
실전 팁
💡 압축 트라이는 단어가 길고 공통 접두사가 적을 때 효과적입니다. 반대로 짧은 단어가 많으면 오히려 복잡도만 증가할 수 있습니다.
💡 배열 기반 최적화도 고려하세요. 알파벳만 다루면 children을 크기 26 배열로 만들어 Map 오버헤드를 제거할 수 있습니다.
💡 대량의 정적 데이터는 빌드 타임에 트라이를 구축하고 JSON이나 바이너리로 직렬화하여 로드 시간을 단축하세요.
💡 메모리 프로파일링 도구(Chrome DevTools, Node.js heap snapshot)로 실제 메모리 사용량을 측정하세요. 이론과 실제는 다를 수 있습니다.
💡 Succinct Data Structure나 LOUDS(Level-Order Unary Degree Sequence) 같은 고급 기법도 있지만, 구현 복잡도가 매우 높으므로 라이브러리 사용을 권장합니다.