허프만(Huffman) 트리 timer 1s memory 128MB

허프만 코딩(Huffman coding)은 텍스트 압축 방법으로,

원본 데이터에서 자주 출현하는 문자는 작은 비트의 코드로 변환하고

출현 빈도가 낮은 문자는 큰 비트의 코드로 변환하여

전체 데이터를 최소한의 비트 수로 압축하는 방식이다.

이 과정에서 각 문자를 표현하기 위한 허프만 트리(Huffman tree)를 구성해야 한다.

예를 들어 ​AAAAAAABBCCCDEEEEFFFFFFG를 압축하려 할 때,

각 문자의 개수는 다음과 같다:

A:7개, F:6개, E:4개, C:3개, B:2개. D:1개, G:1개

이 상황에서 우선 가장 작은 D와 G를 묶어 둘의 합인 2가 부모가 되도록 트리를 구성한다.

이 후 가장 작은 두 노드인 B와 2를 묶어 합인 4이 부모가 되도록 트리를 구성한다.

이와 같은 작업을 반복하여 아래와 같은 트리를 구성한다.

​

최종적으로 전체 트리에 있어서 왼쪽 자식은 0, 오른쪽 자식은 1의 비트를 부여하면 허프만 트리가 완성된다.

이러한 과정을 통하여 문자열을 압축하면 아래와 같은 코드가 나온다.

AAAAAAABBCCCDEEEEFFFFFFG

0000000000000001000100011011011010101111111110101010101001011

각 문자에 대한 비트코드를 출력하는 프로그램을 작성하시오.​​