수학과의 좌충우돌 프로그래밍

KMP 알고리즘 에 이어서 문자열에서 검색에 위한 새로운 방법들을 알아보도록 하겠습니다. 이번에 알아볼 내용은 Trie 자료구조입니다. Trie 자료구조 문자열 집합, {AB, ACD, ACEF, ACEG, HB, HC} 에 대해 Trie 자료구조가 어떻게 그려지는지 살펴보도록 합시다. 시작 부분이 같은 단어끼리 부모를 공유한다면, 다음과 같은 트리 모양을 얻을 수 있습니다. 이 트리에 대하여 탐색을 진행할 경우, 트리의 시간 복잡도는 O(H) (H 는 트리의 높이) 가 될 것입니다. 그리고 트리의 높이는 문자열 집합 중 가장 긴 문자열의 길이와 동일하기 때문에 Trie 자료구조를 사용하면 가장 긴 문자열의 길이를 M 이라 했을 때, O(M) 만에 문자열 검색이 가능합니다. 언제 사용해야 하지? Trie..