세상을 바꾸는 개발자

트라이(Trie)는 문자열의 집합을 표현하는 '트리 자료구조'이다. 원하는 원소를 찾기 위해 자주 이용되는 이진 검색 트리 (STL set, map) 등에서는 원소를 찾는데 **O(logN)**의 시간이 걸리게 된다. 하지만, 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에 원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다. 따라서 여러 번 이 작업을 수행한다면 시간이 오래 걸릴 것이다. 이 단점을 해결하기 위한 문자열 특화 자료구조가 트라이(Trie)이다. 쉽게 말해, "문자열을 빠르게 탐색할 수 있는 자료구조"이다. 트라이(Trie) 자료구조의 장/단점 트라이의 장점은 앞에서도 언급했듯이 당연히 문자열을 빠르게 찾을 수 있다는 점이다. 더불어, ..