트라이 트라이(Trie) 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 따라서 모든 노드가 꼭 키와 연결되지는 않는다. 어떤 노드는 word의 원소에 대한 정보를 담고 있는데 이는 해당 노드까지 탐색하게 되면 탐색 과정에서 등장한 알파벳으로 이뤄진 단어가 현재 트라이에 존재한다는 의미를 나타낸다. 시간 복잡... 문자열자료구조알고리즘트라이백준문자열 [알고리즘] 트라이 개념 및 구현하기 문자열을 저장하고 탐색하기 위한 트리모양 자료구조 자동완성, 사전찾기에 응용됩니다 문자열 탐색에 최적화된 자료구조 입니다 문자마다 노드를 만들어야하기 때문에 저장공간이 많이 필요합니다 탐색 시간복잡도는 문자열의 길이 L에 대해 O(L)만큼만 걸립니다 트라이를 구현할 때 몇가지 규칙이 있습니다. root 노드는 항상 비어있습니다 간선은 추가될 문자입니다 각 노드는 이전 정점의 값 + 간선에 추... 트라이알고리즘알고리즘
트라이(Trie) 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 따라서 모든 노드가 꼭 키와 연결되지는 않는다. 어떤 노드는 word의 원소에 대한 정보를 담고 있는데 이는 해당 노드까지 탐색하게 되면 탐색 과정에서 등장한 알파벳으로 이뤄진 단어가 현재 트라이에 존재한다는 의미를 나타낸다. 시간 복잡... 문자열자료구조알고리즘트라이백준문자열 [알고리즘] 트라이 개념 및 구현하기 문자열을 저장하고 탐색하기 위한 트리모양 자료구조 자동완성, 사전찾기에 응용됩니다 문자열 탐색에 최적화된 자료구조 입니다 문자마다 노드를 만들어야하기 때문에 저장공간이 많이 필요합니다 탐색 시간복잡도는 문자열의 길이 L에 대해 O(L)만큼만 걸립니다 트라이를 구현할 때 몇가지 규칙이 있습니다. root 노드는 항상 비어있습니다 간선은 추가될 문자입니다 각 노드는 이전 정점의 값 + 간선에 추... 트라이알고리즘알고리즘