트라이 (Trie) 자료구조란? 문자열 검색에 최적화된 트리 형태의 자료구조이다. 상위 문자가 하위 문자들의 부모 노드가 되는 트리 구조를 가지고 있다. 'tree', 'trie', 'trim' 이렇게 3개의 문자열을 포함하는 트라이의 예시를 보자. 그림에서 보는 것과 같이, 't' 밑에 'r' 이 하위 노드로 들어가 있고, 'r' 밑에 'i' 와 'e' 가 하위 노드로 들어가 있는 것을 볼 수 있다. 이와 같은 구조를 가지고 있기 때문에, 길이 m의 특정 문자열이 존재하는지 판단하는 것이 O(m) 시간으로 가능하다. 트라이에 필요한 기능 트리 구조에 익숙한 분들이라면 위의 그림만으로도 구현의 방법이 그려졌을 것이다. 트라이의 구현에서는 다음과 같은 기능이 필요하다. (1) 해당 단어가 존재하는지 판단하..