trie자동완성 등에 특화된 자료구조-> 접두사를 기준으로 빠른 탐색 가능 그냥 배열 vs trie단어 탐색: N개의 단어가 있을 때 L길이의 단어를 찾는다면 배열: N개의 단어에 대해 L길이만큼 다 맞는지 확인 -> O(LN) trie: 단어 길이만큼만 분기를 따라가면 됨 -> O(L)접두사 탐색: P길이의 접두사가 주어지고 N개의 단어 중 찾는다면 배열: P길이의 접두사 비교를 N개의 단어에 대해 모두 확인 -> O(PN) trie: 얘도 접두사 만큼만 따라가면 됨 -> O(P) (= O(L))메모리 차지 배열은 그냥 저장하면 되지만 trie는 노드별로 분기를 저장해야 되기 때문 예) 영어를 저장하는 trie는 각 노드마다 26개의 공간이 있어야 한다. ..