자료구조 - 트라이(Trie)
1. 트라이(Trie)란? 트라이(Trie)는 효율적인 문자열 저장 및 탐색이 가능한 자료구조의 형태이다. 우리가 수많은 문자열을 저장하였는데 입력으로 어떤 문자열이 주어졌을 때, 그것이 내가 저장한 구조에 포함된 문자열인지 어떻게 알 수 있을까? 아래와 같은 방식이 있을 것이다. ① 단순 비교 전체 문자열의 맨 처음부터 끝까지 개별 문자를 비교하는 방식 최대 문자열 길이 m, 전체 문자 개수 n개 시 시간복잡도 : 최악의 경우 O(nm) ② 이진 탐색 기법 전체 문자열을 사전 순으로 배열 저장 후, 중간 값과 비교해 사전적으로 이전이면 좌측의 반 / 이후면 우측의 반으로 비교하는 방식을 반복 최대 문자열 길이 m, 전체 문자 개수 n개 시 시간복잡도 : 정렬 O(nmlogn) / 탐색 O(mlogn) ..
