NullNull

트라이 자료구조 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 문자열을 한 자리씩 뽑아내어 트리 형태로 저장한다. 각 노드의 자식들을 탐색하며 저장된 문자열을 얻는다. 즉, 트리의 형태로 문자열을 저장하고 탐색할 수 있는 자료구조가 트라이이며 각 노드의 자식들에는 다음에 나올 문자에 대한 노드가 연결되어 있다. 트라이 시간복잡도 트라이는 주로 많은 문자열들을 저장한 뒤에 특정 문자열이 그 안에 속하는지를 확인할 때 많이 사용된다. 예를 들어 길이가 L인 문자열 M개를 저장해두고 길이가 L인 임의의 문자열 A가 M개 안에 속해있는지 확인한다고 가정해 보자. 저장 시 시간복잡도 : O(L * M) 한 개의 문자열을 저장할 때 L만큼의 시간이 걸린다. 문자열을 문자의..