Algorithm Guidecomplexity: O(n log n)

허프만 코딩 (Huffman Coding)

자주 등장하는 문자에 짧은 비트, 드문 문자에 긴 비트를 부여해 데이터를 압축합니다. 빈도가 가장 작은 두 노드를 반복해 합쳐 트리를 만드는 그리디 전략으로 최적 접두사 코드를 생성합니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Huffman Coding

허프만 코딩 시작. 빈도 a:5, b:2, c:1, d:1. 가장 작은 둘을 반복해 합치며 트리를 만듭니다.

Logic Node1 / 5

Live Python

1import heapq

3def huffman(freq):

4 heap = [[w, sym] for sym, w in freq.items()]

5 heapq.heapify(heap)

6 while len(heap) > 1:

7 lo = heapq.heappop(heap) # 가장 작은 둘

8 hi = heapq.heappop(heap)

9 merged = [lo[0] + hi[0], lo, hi]

10 heapq.heappush(heap, merged) # 합쳐 다시 넣기

11 return heap[0]

02 쉽게 이해하기

For Everyone

🔑비유

자주 쓰는 말은 짧게, 드문 말은 길게 줄여 쓰는 속기와 같습니다.

💡쉽게 말하면

빈도가 작은 둘을 반복해 합쳐 트리를 만들고, 자주 나오는 글자에 짧은 비트를 부여합니다. 그 결과 전체 데이터 길이가 최소가 돼요.

📍어디에 쓰나

파일 압축(ZIP·JPEG), 데이터 전송 인코딩.

03 파이썬 구현 코드

허프만 코딩 (Huffman Coding)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

import heapq

def huffman(freq):
    heap = [[w, [sym, ""]] for sym, w in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heapq.heappop(heap)[1:])

Guide Progress0%