목록trie (1)

포시코딩

Trie(트라이)

개요 여러 개의 문자열 중 특정 문자열을 찾을 때 효과적인 트라이(Trie) 자료구조에 대해 알아보자 먼저, 이름은 retrieval(검색) tree에서 따왔다 정도의 유래가 있는듯하다. 위에서 말한바와 같이 여러 개의 문자열 중 특정 문자열을 찾을 때 하나하나 확인한다면 O(n) (n은 list의 길이)의 시간복잡도를 가지거나 정렬 후 이진 탐색을 사용한다면 O(nlog n)의 시간복잡도를 가지는 반면, 트라이의 경우 최선일 경우 O(1), 최악일 경우에도 O(m) (m은 문자열의 길이) 안에 할 수 있다고 한다. 따라서, 문자열이 아주 길거나 자동 완성 및 검색어 추천 기능 등에서 Trie 자료구조를 통해 효과를 볼 수 있다. 형태 문자열 집합 {'rebro', 'replay', 'hi', 'high..
자료구조알고리즘/이론 2023. 7. 10. 09:03
이전 Prev 1 Next 다음