Let IT Begin

* Python을 기준으로 합니다 트라이 (Trie) - 개념 트라이 : 문자열 탐색을 위한 트리 형태의 자료구조 어떠한 문자열 내에서 특정 단어를 검색한다고 하자 - 직관적으로 문자별 단순 비교를 사용하는 경우 $O(n^{2})$의 time complexity를 가짐 - 대신 트라이 구조를 적용하면 $O(n)$ 내에 탐색이 가능함 이때 트라이는 일반적으로 사용되는 이진 트리 형식이 아닌 다진 트리($m$-ary Tree) 형태를 가짐 장점 - 트라이를 구성하면 완전히 일치하는 문자열이 아니라 일부를 생략하더라도 탐색이 가능함 - 문자별로 트리가 만들어지기 때문에 자동적으로 정렬되는 효과가 있음 단점 - 문자의 수가 늘어날수록 메모리를 많이 사용함 - 구현 1. 노드 정의 트라이는 이진 트리가 아니라, ..