[Algorithm] 트라이(Trie)

[Algorithm] 트라이(Trie) 개념 트라이(Trie) 트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 아래와 같이 트리의 루트에서부터 자식들을 따라가면 문자열이 생성되는데 해당 문자열은 트라이에 저장되어있다고 한다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있다. 문자열 탐색을 할때 빠르게 할 수 있고 효율적이다. 각 노드에서 자식들에 대한 포인터들을 배열로 저장하고 있어서 저장 공간의 크기가 크다는 단점이 있다. 검색어 자동완성, 사전에서 찾기 그리고 문자열 검사 같은 부분에서 사용할 수 있다. 시간 복잡도 제일 긴 문자열의 길이를 L, 총 문자열들의 수를 M이라고 하자. 트라이 생성: O(M*L). 문자열 개수 * 제일 긴 문자..