[Algorithm] Trie(트라이) 자료구조
# 문자열을 찾을때 사용하는 알고리즘이 여러가지 있는데, 대표적으로 KMP, 라빈카프, 보이어-무어, BruteForce, Trie등이 있다. 전체 문자열 길이를 N, 찾고자하는 패턴길이를 M이라 하면 BruteForce는 O(NM) / KMP는 O(N) + 전처리 / 보이어-무어는 O(N/M), 최악 O(N) / 라빈카프는 O(N)이다. # 이번에 소개할 자료구조는 Trie(트라이)라고 하는 자료구조인데, 우선 Trie라는 말은 retrieval(탐색)에서 따온 말이라고 한다. 트라이는 트리구조를 사용해서 문자열을 저장하는데, 시간복잡도가 가장 긴 문자열의 길이를 L이라 했을때 O(L)밖에 걸리지 않는다. # 우선 'fire', 'firefox', 'frodo', 'frost', 'fry'를 저장했을 ..
