트라이 (Trie) [ 크래프톤 정글 20일차 ]

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

데이터 구조

대상자

• 소프트웨어 개발자, 알고리즘 학습자
• 중급~고급 수준의 자료구조 이해 요구

핵심 요약

• 트라이(Trie)는 문자열을 문자 단위로 분할하여 계층적 트리 구조로 저장하는 자료구조
• 탐색, 삽입, 삭제 시간 복잡도는 O(L) (L: 문자열 길이)
• 공통 접두사를 공유하는 노드 구조로 메모리 사용량이 높은 편이지만, 자동완성(Autocomplete)에 최적화

섹션별 세부 요약

1. 트라이의 정의

• 트라이(Trie)는 Prefix Tree로 불리며, 문자열의 공통 접두사를 기반으로 데이터를 저장
• 예시: ["cat", "can", "cap", "dog"] → 공통 접두사 'c'를 가진 노드 공유
• 해시테이블과의 차이: 문자열 자체를 인덱싱하여 탐색, 삽입, 삭제 수행

2. 트라이의 특징

• 노드 하나당 하나의 문자만 저장 (계층적 구조)
• 공통 접두사를 가진 문자열은 동일한 경로 공유
• 메모리 효율성 대신 높은 메모리 사용량이 단점

3. 트라이와 자동완성(Autocomplete)

• Autocomplete는 입력된 접두사(prefix) 기반으로 가능한 단어를 제안하는 기능
• 트라이의 구조가 접두사 기반 탐색에 최적화되어 활용됨
• 예시: "ca" 입력 시 "cat", "can", "cap" 제안

4. 구현 예제 (Python)

• TrieNode 클래스: children (딕셔너리), is_end (불리언) 속성 포함**
• Trie 클래스: insert, search, autocomplete 메서드 구현**
• autocomplete(prefix) 메서드: DFS로 접두사 기반 후보 단어 탐색**

결론

• 트라이 구조는 자동완성, 검색어 추천 등에 유리하지만, 메모리 사용량을 고려한 설계 필요
• TrieNode 및 Trie 클래스 구현은 문자열 처리 효율성을 극대화하는 핵심 패턴