Algorithm Guidecomplexity: O(n log n)

허프만 코딩 (Huffman Coding)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

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 Understand It Simply

For Everyone

🔑Analogy

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

💡In Plain Words

빈도가 작은 둘을 반복해 합쳐 트리를 만들고, 자주 나오는 글자에 짧은 비트를 부여합니다.

그 결과 전체 데이터 길이가 최소가 돼요.

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 허프만 코딩 (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:])

04 Frequently Asked Questions

FAQ

What is 허프만 코딩 (Huffman Coding)?+

What is the time complexity of 허프만 코딩 (Huffman Coding)?+

The time complexity of 허프만 코딩 (Huffman Coding) is O(n log n). Follow the step-by-step visualization to see exactly why.

Where is 허프만 코딩 (Huffman Coding) used?+

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

What's a simple analogy for 허프만 코딩 (Huffman Coding)?+

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

→ Greedy — see allRelated

🎯동전 거스름돈 (Coin Change)

O(n)

🎯활동 선택 (Activity Selection)

O(n log n)

Guide Progress0%