자료구조

[Data Structure] Trie

이번 아티클에서는 자료구조 중 하나인 트라이(Trie)에 대해 알아본다. 트라이의 핵심우선 용어에 대해 이해하는 것이 도움이 될 것 같다. Trie는 Retrieval Tree에서 추출한 단어라고 한다. 즉, 트라이는 트리이면서 검색(Retrieval)을 위해 사용될 수 있다. 그렇다면 트라이가 어떻게 검색에 활용될 수 있다는 것일까? 보통은 문자열 검색에서 트라이를 많이 활용하게 된다. 필자를 포함하여 대부분의 사람들은 검색창 자동완성 기능을 사용해 본 경험이 있을 것이다. 'coffee'를 검색하려고 할 때, 'cof' 까지만 치더라도 coffee라는 단어가 자동완성이 된다. 그렇다면 수많은 단어들 사이에서 cof가 coffee와 연관되어 있다는 사실은 어떻게 알아낼까? 사전에 기록된 모든 단어에 대..