tobey2j0   1년 전

이 문제의 아이디어가 n을 (k-1)로 나눈 나머지가 1이 아닐 때, 없는 문자 몇 개를 추가하여 n을 (k-1)로 나눈 나머지가 1이 되도록 한 후 2진법 허프만 인코딩과 같이 그리디하게 자식을 k개 가지는 노드를 생성하는 방식으로 각 문자에 k진법 문자열을 할당하는 것으로 알고 있습니다.

n=2인 경우는 어차피 자식이 2개밖에 되지 않으니까 기존 허프만 인코딩의 아이디어가 이해가 되었는데, n>=3인 경우는 자식이 2개일 수도 있고 3개일 수도 있고 하다 보니까 계속 생각을 해봐도 위 아이디어가 무조건 맞을거라는 확신이 들지 않더라고요.

예를 들어 아래와 같이 처음부터 쭉 그리디하게 k개의 자식을 가지는 노드 생성 후 그냥 마지막에서 다 합치는 방식으로 말이죠..

물론 제가 생각한 방식이 틀렸다는 건 알고 있지만, 꼭 아래에서 제가 제시한 예시가 아니더라도, 왜 그 아이디어가 항상 성립을 하는 건지 알고 싶습니다.

zenith82114   1년 전

개수가 가장 작은 k개를 선택하는 것을 반복하는 그리디성이 가장 중요한 아이디어이고, k가 달라져도 그 원리는 변함이 없습니다. k=2일 때의 최적성 증명을 읽어보시면 도움이 될 것입니다.

tobey2j0   1년 전

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일때는 그게 자명하지 않아서 그 부분이 의문인 것입니다.

혹시 알려 주실 수 있을까요...

doju   1년 전

트리에 리프 노드가 아니면서 자식이 k개보다 적은 노드가 있다면, 이 노드 아래에 빈도가 0인 문자(이하 더미 문자)를 붙여서 k개를 채울 수 있습니다. 이렇게 트리의 모든 노드가 리프 노드거나 자식을 k개 갖도록 만들었다고 가정합니다. 이제 다음과 같은 행동을 반복합니다.

  • 만약 어떤 빈도가 0이 아닌 문자가 더미 문자보다 더 낮은 위치에 있다면, 둘을 맞바꾸는 것이 반드시 이득이므로 바꿉니다.
  • 만약 같은 깊이에 더미 문자가 k개 이상 있다면, 같은 깊이의 다른 노드들과 적당히 맞바꾸어 k개를 한 부모 노드 아래로 모읍니다. 그러면 이 k개의 더미 문자를 한 단계 높은 새로운 더미 문자로 합칠 수 있습니다.

이를 계속 반복하면, 이 트리는 여전히 모든 노드가 리프 노드거나 자식을 k개 갖고 있으며 더미 문자는 가장 낮은 깊이에만 k개 미만으로 남아 있는 상태가 됩니다. 그리고 이 트리는 원래 트리보다 같거나 더 좋은 답입니다.

tobey2j0   1년 전

오 감사합니다!

댓글을 작성하려면 로그인해야 합니다.