트라이 검색 결과

해당 글 2건
trie에서 공간을 줄이기 위해 포인터를 어떻게 쪼갤까요?

안녕하세요. 백준에서 chogahui05로 활동하고 있는 조경완입니다. 트라이에서 x진법으로 쪼갠다. 무슨 소리일까요? 사실 Trie가 어떤 것을 처리하기 위한 자료구조인지는, 카카오 문제에 출제되어서 익숙하신 분들이 많으실 거라고 생각합니다. 여기서 한 단계 더 깊이 들어가 보도록 하겠습니다. 공간을 줄이기 위해서는 어떻게 잘 쪼개야 할까요? 먼저 소문자로만 이루어진 문자열들을 Trie에 넣었을 때 상황을 생각해 보겠습니다. 문자열들의 길이 합은 10만을 넘지 않는다고 해 보겠습니다. 그리고 소문자만 나온다고 해 보겠습니다. 그러면, 다음과 같이 정적 Trie를 구축할 수 있을 겁니다. 여기서 26은 다음을 의미합니다. 'a'가 나왔을 때, 'b'가 나왔을 때, ... , 'z'가 나왔을 때 어디로 갈..
자료알고/자료구조 2020. 5. 5. 21:31
k번째 숫자 구하기 : 트라이(Trie) 구조를 이용해 봅시다.

수 x가 추가되고 제거됩니다. k번째로 작은 수를 구해야 하는 쿼리가 있습니다. 아니면, 수 x가 있는지 찾아야 합니다. 어떻게 해야 할까요? 물론, offline이 가능하면 정렬하고 좌표 압축한 다음에 세그먼트 트리를 돌릴 수 있어요. 하지만, online으로 해결해야 하는 경우, 정렬 후 좌표압축 스킬이 통하지 않습니다. 이 때, 우리는 수 x를 32bit 범위 내라면 32, 64bit 범위 내라면 길이 64의 2진수 문자열로 변환할 수 있습니다. 이 때, 우리는 Trie라는 자료구조를 생각할 수 있습니다. 이 Trie는 올해 카카오 4번에 나왔던 structure 이기도 합니다. Skip List는 상대적으로 구현하기 까다로우니, 논외로 합시다. 예를 들어서, 13을 넣는다고 생각해 봅시다. 그러면..
자료알고/자료구조 2019. 12. 5. 20:12