Oh My Algorithm
Algorithm Guidecomplexity: O(n log n)

허프만 코딩 (Huffman Coding)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step
Huffman Coding
5a2b1c1d

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

Logic Node1 / 5

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:])

04 자주 묻는 질문

FAQ
허프만 코딩 (Huffman Coding)란 무엇인가요?+

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

허프만 코딩 (Huffman Coding)의 시간복잡도는 어떻게 되나요?+

허프만 코딩 (Huffman Coding)의 시간복잡도는 O(n log n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

허프만 코딩 (Huffman Coding)은(는) 어디에 사용하나요?+

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

허프만 코딩 (Huffman Coding)를 쉽게 비유하면?+

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

→ 그리디 전체 보기Related
🎯동전 거스름돈 (Coin Change)
O(n)
🎯활동 선택 (Activity Selection)
O(n log n)
Guide Progress0%