Trie 썸네일형 리스트형 트라이(Trie) 문자열 관련 알고리즘은 정말 다루기 힘든편에 속한다. 하지만 그중에도 잘만 이해하면 유용하게 사용할 수 있는 알고리즘이 몇있다. 그중에서 트라이(Trie)에 대해서 얘기해보고자 한다. 트라이 - 나무위키https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4 트라이 알고리즘은 여러 단어들이 주어진 경우, 특정 단어가 예시로 주어진 단어들 중에 포함되는가를 빠르게 파악할 수 있는 알고리즘이다. 예를들어 n개의 단어가 주어져있고, 각 문자열의 길이가 m인 경우 단순하게 이 단어들중에 특정 단어가 포함되어있는지 확인하려면 최대 O(nm)의 시간 복잡도를 갖게된다. 하지만 트라이를 사용하면 시간복잡도가 O(m)으로 압도적으로 단축되게 된다. 어떻게 이렇게 시간이 줄어들 수 있는지 생.. 이전 1 다음
