'로그' 태그의 글 목록

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