매일 매일 성장하는 섭섭군

Trie(트라이) Trie의 개요 Trie 는 트리 자료구조 중 하나이다. 특히 여러개의 문자열을 저장하는 자료구조인데 특정 문자열을 검색할 때 효율적이다. 가령 최대 길이가 m인 문자열 n개가 있는 집합에서 길이가 m인 임의의 문자열이 있는지 확인하려면 어떻게 해야할까? 단순히 직관적인 방법으로 하나씩 꺼내서 비교하면 된다. 하지만 최악의 경우 O(nm)의 시간복잡도가 소요된다. 그렇다면 Trie는 어떻게 문자열을 저장하길레 문자열을 검색할때 효율적일까? 바로 우리가 사전에서 단어를 찾듯이 문자열을 저장한다. 우리는 사전에서 "Apple"이란 단어를 찾을 때 다음과 같이 찾을것이다. 1. A가 있는 곳을 찾는다. 2. 두번째 글자가 p인 곳을 찾고 세번째가 p인 곳을 찾는다. 3. 마지막 글자까리 위와..