Algorithm Guidecomplexity: O(n log n)

허프만 코딩 (Huffman Coding)

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

01허프만 코딩 (Huffman Coding)

알고리즘 작동 원리 탐색

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

가장 작은 c(1)와 d(1)를 합쳐 부모(2)를 만듭니다.

다음으로 작은 b(2)와 방금 만든 노드(2)를 합쳐 부모(4)를 만듭니다.

마지막으로 a(5)와 노드(4)를 합쳐 루트(9)를 만듭니다. 트리 완성.

왼쪽=0, 오른쪽=1로 읽으면 a=0, b=10, c=110, d=111. 자주 쓰는 a가 가장 짧은 코드를 받아 전체 길이가 줄어듭니다.

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]

1 / 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)