Trie 썸네일형 리스트형 [자료구조]트라이(Trie) 트라이(Trie)는 문자열에서의 검색을 빠르게 해주는 자료구조입니다. 우리는 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간만에 원하는 데이터를 검색할 수 있습니다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대 길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것입니다. 우리는 문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있습니다. 트라이라는 명칭은 Retrieval에서 유래했다고 합니다. 트라이가 retrieve(탐색)하는데 유용한 걸 생각하면 납득이됩니다. 자 그러면 트라이는 어떻게 문자열의 검색을 O(M)만에 처리해 줄 수 있을까요? 아래 그림은 문자열 집합 = {"AE" , "ATV", "ATES", .. 더보기 BOJ)9202 Boggle 문제: icpc.me/9202 점수를 얻을 수 있는 문자열 셋이 주어진 뒤 Boggle 보드가 주어질 때 주어진 Boggle 보드에서 얻을 수 있는 최고점수 가장 긴 문자열 찾은 단어의 수를 출력하는 문제이다. 단어 사전에 단어가 30만개 까지 들어올 수 있으므로 트라이를 이용하여 해결하면 쿼리를 매번 최대 단어의 길이안에 처리해줄 수 있다. 우리는 단어 사전의 모든 단어들을 Trie에 저장해 준 후 Boggle 보드에서 Bruteforce를 통하여 모든 경우를 탐색하여 나올 수 있는 문자열들을 set에 저장해 준 뒤 답을 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505.. 더보기 BOJ)5052 전화번호 목록 문제: icpc.me/5052 전화번호 목록이 주어질 때 전화번호들이 일관성을 띄는지 조사하는 문제이다. 우리는 트라이를 활용하여 전화번호 목록들을 전부 트라이에 insert 한 뒤 모든 전화번호를 검색하여 문자열이 끝나는 지점에서 아직 더 탐색이 가능한 경우가 존재한다면 일관성이 없다고 결정해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include #define MAX_N 10000using namespace std;struct Trie{ Trie* next[10]; bool term; Trie() : term.. 더보기 BOJ)13505 두수 XOR 문제: icpc.me/13505 N개의 수 중에서 두 수를 정해 XOR한 값이 가장 크게 하는 문제이다. 두수가 XOR을 하여 가장 큰 수가 되려면 서로 다른 비트가 가장 많아야 할 것이다. 트라이를 이용하여 모든 수를 비트 순서대로 저장 한 후 이후 모든 수에 대해서 자기와 다른 비트를 따라가도록 하면 된다. 이때 가장 큰 수가 되야 하므로 비트는 높은 자리 수 부터 검사한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include #include #incl.. 더보기 이전 1 다음
