알고리즘, 자료구조/Trie 자료구조1 Trie 자료구조 [Python / 파이썬] 1. Trie 자료구조란? ※ 입력되는 문자열을 Tree 형식으로 만들어 진행되어 보다 빠르게 문자열 검색이 가능한 자료구조이다. 보통 list에서 문자열이 존재하는지 확인하기 위해서는 O(n) (n은 list의 길이)이라는 시간이 걸리는데 Trie 알고리즘을 사용하면 O(m) (m은 문자열의 길이) 이라는 짧은 시간이 소요되기 때문에 엄청 효율적이라고 할 수 있다. 2. 어떤 경우에 적합한가? ※문자열을 검색하는 문제에서 입력되는 문자열이 많을 경우 자주 사용된다. 빠른 시간복잡도 덕분에 검색엔진 사이트에서 제공하는 자동 완성 및 검색어 추천 기능에서 Trie 자료구조를 사용한다. 3. Trie 자료구조의 형태 1. Trie 알고리즘은 노드를 이용한 Tree 형태로 이루어져 있다. 2. 문자열의 끝을 .. 2022. 1. 3. 이전 1 다음
