28340번 - K-ary Huffman Encoding
n=2일 때 최적성 증명을 살펴봤는데 귀류법으로 증명하더라고요.
Depth가 가장 큰 두 leaf node i, j 보다 빈도수가 작은 다른 leaf node k 를 가정하겠습니다. i 와 k 를 Huffman tree에서 교체 시 encoding 결과가 줄어듭니다. 따라서 Huffman encoding이 최적해라는 사실에 모순됩니다.
출처: https://ttl-blog.tistory.com/1004 [Shin._.Mallang:티스토리]
그런데 위 증명은 빈도가 가장 작은 것들을 선택해야 하는 이유를 증명하는 것이고, 제가 궁금한 것은 왜 굳이 'k개씩' 선택하는 것이 최적해인지입니다.
k=2일 때는 당연히 2개씩 밖에 선택하지 못하니까 자명한데, k>=3일때는 그게 자명하지 않아서 그 부분이 의문인 것입니다.
혹시 알려 주실 수 있을까요...
트리에 리프 노드가 아니면서 자식이 k개보다 적은 노드가 있다면, 이 노드 아래에 빈도가 0인 문자(이하 더미 문자)를 붙여서 k개를 채울 수 있습니다. 이렇게 트리의 모든 노드가 리프 노드거나 자식을 k개 갖도록 만들었다고 가정합니다. 이제 다음과 같은 행동을 반복합니다.
이를 계속 반복하면, 이 트리는 여전히 모든 노드가 리프 노드거나 자식을 k개 갖고 있으며 더미 문자는 가장 낮은 깊이에만 k개 미만으로 남아 있는 상태가 됩니다. 그리고 이 트리는 원래 트리보다 같거나 더 좋은 답입니다.
댓글을 작성하려면 로그인해야 합니다.
tobey2j0 1년 전
이 문제의 아이디어가 n을 (k-1)로 나눈 나머지가 1이 아닐 때, 없는 문자 몇 개를 추가하여 n을 (k-1)로 나눈 나머지가 1이 되도록 한 후 2진법 허프만 인코딩과 같이 그리디하게 자식을 k개 가지는 노드를 생성하는 방식으로 각 문자에 k진법 문자열을 할당하는 것으로 알고 있습니다.
n=2인 경우는 어차피 자식이 2개밖에 되지 않으니까 기존 허프만 인코딩의 아이디어가 이해가 되었는데, n>=3인 경우는 자식이 2개일 수도 있고 3개일 수도 있고 하다 보니까 계속 생각을 해봐도 위 아이디어가 무조건 맞을거라는 확신이 들지 않더라고요.
예를 들어 아래와 같이 처음부터 쭉 그리디하게 k개의 자식을 가지는 노드 생성 후 그냥 마지막에서 다 합치는 방식으로 말이죠..
물론 제가 생각한 방식이 틀렸다는 건 알고 있지만, 꼭 아래에서 제가 제시한 예시가 아니더라도, 왜 그 아이디어가 항상 성립을 하는 건지 알고 싶습니다.