[개발자 기술 면접 대비] 📦 허프만 코딩(Huffman Coding)이란?

문자의 등장 빈도를 기반으로 데이터를 압축하는 대표적인 손실 없는 압축 알고리즘입니다.

---

1️⃣ 개념 요약

• 자주 등장하는 문자에는 짧은 이진 코드,
• 드물게 등장하는 문자에는 긴 이진 코드를 부여하여
• 전체 메시지의 평균 길이를 최소화하는 것이 목표입니다.

이 방식을 통해 데이터를 효율적으로 저장하거나 전송할 수 있습니다.

---

2️⃣ 동작 원리

1. 각 문자와 빈도 수(가중치)를 기반으로 노드를 생성
2. 가장 낮은 빈도를 가진 두 노드를 하나의 부모 노드로 합침
3. 이 과정을 반복하여 하나의 이진 트리(허프만 트리)를 생성
4. 왼쪽 경로에는 0, 오른쪽 경로에는 1을 부여하여 각 문자에 대한 코드 생성

---

3️⃣ 주요 특징

특징 설명

✅ 접두부 코드 (Prefix Code)	어느 한 코드도 다른 코드의 접두어가 될 수 없음 → 디코딩 시 혼동 없음
✅ 최적 코드 (Optimal Code)	전체 메시지를 인코딩했을 때 총 비트 수가 최소화
✅ 이진 트리 기반	등장 빈도가 낮은 문자부터 트리를 구성
✅ 무손실 압축	압축된 데이터를 정확히 원래대로 복원 가능

---

4️⃣ 간단한 예시

예를 들어, 아래와 같은 문자 빈도가 있다고 가정해보겠습니다:

문자 빈도

a	5
b	2
r	2
c	1
d	1

→ 허프만 트리를 구성한 뒤, 문자마다 다음과 같은 코드가 부여될 수 있습니다:

문자 허프만 코드

a	0
b	100
r	101
c	110
d	111

• 자주 나오는 a는 짧은 코드(1비트)
• 드물게 나오는 c, d는 긴 코드(3비트)

→ 전체 메시지를 인코딩했을 때 총 비트 수가 최소화됨

---

🎯 면접용 핵심 정리 답변

“허프만 코딩은 문자의 등장 빈도를 기반으로 이진 코드를 부여하여 데이터를 압축하는 알고리즘입니다.
자주 등장하는 문자엔 짧은 코드, 드물게 등장하는 문자엔 긴 코드를 부여하여 전체 평균 비트 수를 줄이며, 이진 트리 기반으로 구성됩니다.
접두어가 겹치지 않는 ‘접두부 코드’로 만들어지기 때문에 안정적인 디코딩이 가능하고, JPEG, MP3 등 실제 압축 기술에도 사용됩니다.”