Trie (1) 썸네일형 리스트형 [알고리즘] 트라이(Trie) 개요 및 개념 여러 개의 문자열이 등록된 사전을 만들고 특정 문자열이 이 사전안에 등재된 문자열인지 확인하려면 어떻게 해야할까요? 단순히 일일이 비교해서 확인해보면 되지만 이 경우 최악의 경우에 \( O(nm) \)의 수행시간이 필요합니다. 혹은 이진 탐색을 사용하여 \( O(m\textbf{log}n) \)으로 단축시킬 수 있지만 정렬 과정에서 \( O(mn\textbf{log}n) \)의 시간이 걸리게 됩니다. 이러한 문자열 검색의 시간복잡도를 단축시키기 위해서는 프레드킨이 명명한 Retrieval Tree 알고리즘이 필요합니다. (Prefix Tree, Digital Search Tree 라고도 합니다.) 트라이(Trie)란? 트라이는 탐색 트리의 일종으로 문자열을 빠르게 검색할 수 있는 자료 구조입니다. K진 .. 이전 1 다음
