# [06-03] 그리디 (Greedy)
그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하여 최적해를 찾는 직관적인 알고리즘 설계 기법입니다.
🎯 그리디란 무엇인가
그리디의 기본 개념
그리디(Greedy) 알고리즘은 "지금 당장 가장 좋은 것"을 선택하는 방법입니다. 탐욕 알고리즘이라고 부르기도 합니다.
실생활 비유:
마트에서 1,000원으로 최대한 많은 사탕 사기:
그리디 접근:
1. 가장 싼 사탕부터 산다
2. 돈이 남으면 그 다음 싼 사탕
3. 돈이 떨어질 때까지 반복
예:
100원 사탕 × 10개 = 1,000원 ✓
비그리디 접근:
"200원짜리 5개가 더 맛있을 수도..."
→ 복잡하게 고민또 다른 예시:
- 등산: 항상 가장 가파른 길로 올라가기 (정상에 가장 빨리?)
- 청소: 가장 더러운 곳부터 청소
- 공부: 가장 쉬운 과목부터 공부
그리디의 특징
장점:
- ✅ 단순함: 구현이 직관적이고 쉽습니다
- ✅ 빠름: 대부분 O(n) 또는 O(n log n)
- ✅ 메모리 효율: 추가 메모리가 거의 필요 없습니다
단점:
- ⚠️ 항상 최적해가 아님: 지역 최적이 전역 최적이 아닐 수 있습니다
- ⚠️ 증명 필요: 그리디가 최적해를 보장하는지 증명해야 합니다
핵심 질문: "매 순간의 최선이 전체의 최선인가?"
그리디가 실패하는 경우
예시: 동전 문제
동전: 10원, 7원, 1원
목표: 15원 만들기
그리디 접근 (큰 것부터):
10원 × 1 = 10원
7원 × 0 (10원 쓰고 5원 남아서 불가)
1원 × 5 = 5원
→ 총 6개 ✗
최적해:
7원 × 2 = 14원
1원 × 1 = 1원
→ 총 3개 ✓
그리디가 실패!예시: 등산로
정상(100m)
/ \
/ \
70m 80m
| |
| |
시작 시작
그리디: "가장 가파른 길로!"
→ 80m 선택
→ 막다른 길! ✗
최적해: 70m 길
→ 정상 도착 ✓💰 거스름돈 문제
문제 설명
문제: 거스름돈을 최소 개수의 동전으로 만들기
거스름돈: 1,260원
동전: 500원, 100원, 50원, 10원
목표: 최소 동전 개수그리디 접근
전략: 큰 동전부터 최대한 사용
def make_change(amount):
"""
거스름돈을 최소 동전 개수로 만들기
그리디 전략: 큰 동전부터 사용
amount: 거스름돈 액수
Returns: 사용한 동전 리스트
"""
# 동전 종류 (큰 것부터)
coins = [500, 100, 50, 10]
result = []
for coin in coins:
# 현재 동전으로 최대한 거슬러주기
while amount >= coin:
result.append(coin)
amount -= coin
return result
# 사용 예시
change = make_change(1260)
print(change) # [500, 500, 100, 100, 50, 10]
print(f"동전 개수: {len(change)}") # 6개
# 단계별 과정:
# 1,260원
# → 500원 사용: 760원 남음
# → 500원 사용: 260원 남음
# → 100원 사용: 160원 남음
# → 100원 사용: 60원 남음
# → 50원 사용: 10원 남음
# → 10원 사용: 0원왜 그리디가 최적인가?
한국 동전 시스템에서는 그리디가 항상 최적해를 보장합니다.
이유: 큰 동전이 작은 동전의 배수 관계
500 = 100 × 5
100 = 50 × 2
50 = 10 × 5
이런 구조에서는:
"큰 것을 1개 = 작은 것 여러 개"
→ 큰 것을 쓰는 게 항상 유리증명 (귀류법):
만약 500원을 안 쓰고 최적해를 만들 수 있다면?
→ 100원을 5개 이상 써야 함 (500원 대신)
→ 100원 5개 = 500원 1개
→ 모순! 500원 쓰는 게 항상 더 적음📅 회의실 배정 문제
문제 설명
문제: 하나의 회의실에 최대한 많은 회의 배정하기
회의 목록 (시작, 종료):
A: 09:00 - 10:00
B: 09:30 - 11:00
C: 10:00 - 11:30
D: 10:30 - 12:00
E: 11:00 - 12:30
F: 12:00 - 13:00
목표: 최대 회의 개수그리디 접근
잘못된 전략들:
전략 1: 빨리 시작하는 순서 → A(9-10), B(9:30-11)...B가 C, D를 막음 ✗
전략 2: 짧은 회의 먼저 → 1시간짜리만 선택해도 최적 아닐 수 있음 ✗
전략 3: 겹치는 회의가 적은 것 → 계산 복잡, 최적 보장 안 됨 ✗올바른 전략: 빨리 끝나는 회의 먼저!
왜? 빨리 끝나야 다음 회의를 받을 수 있음
1. 회의를 종료 시간 순으로 정렬
2. 종료 시간이 빠른 것부터 선택
3. 겹치지 않으면 계속 선택구현
def schedule_meetings(meetings):
"""
최대 회의 개수 배정
그리디 전략: 빨리 끝나는 회의 우선
meetings: [(시작, 종료), ...] 리스트
Returns: 선택된 회의 리스트
"""
# 1. 종료 시간 기준 정렬
# 종료 시간이 같으면 시작 시간 빠른 순
meetings.sort(key=lambda x: (x[1], x[0]))
# 1순위 (x[1]): 회의가 종료되는 시간을 기준으로 오름차순 정렬
# 2순위 (x[0]): 종료 시간(x[1])이 같다면, 시작되는 시간(x[0])을 기준으로 오름차순 정렬
result = []
last_end_time = 0
for start, end in meetings:
# 2. 이전 회의가 끝난 후 시작하는 회의만 선택
if start >= last_end_time:
result.append((start, end))
last_end_time = end
return result
# 사용 예시
meetings = [
(9, 10), # A
(9.5, 11), # B
(10, 11.5),# C
(10.5, 12),# D
(11, 12.5),# E
(12, 13) # F
]
selected = schedule_meetings(meetings)
print(f"선택된 회의: {selected}")
# [(9, 10), (10, 11.5), (12, 13)]
print(f"회의 개수: {len(selected)}") # 3개
# 단계별 과정:
# 정렬 후: [(9, 10), (9.5, 11), (10, 11.5), (10.5, 12), (11, 12.5), (12, 13)]
#
# (9, 10) 선택 → last_end = 10
# (9.5, 11): 9.5 < 10 ✗ (겹침)
# (10, 11.5): 10 ≥ 10 ✓ 선택 → last_end = 11.5
# (10.5, 12): 10.5 < 11.5 ✗
# (11, 12.5): 11 < 11.5 ✗
# (12, 13): 12 ≥ 11.5 ✓ 선택 → last_end = 13왜 그리디가 최적인가?
증명 (교환 논증):
최적해를 O = [o1, o2, ..., ok]라 하자
그리디 해를 G = [g1, g2, ..., gm]라 하자
증명할 것: m = k (그리디도 최대)
1. g1은 가장 빨리 끝나는 회의
2. o1을 g1로 교체해도 여전히 유효한 해 (g1이 더 빨리 끝나므로 나머지에 영향 없음)
3. 귀납적으로 모든 oi를 gi로 교체 가능
4. 따라서 m ≥ k
∴ 그리디가 최적!🎒 분할 가능 배낭 문제
문제 설명
문제: 배낭에 최대 가치를 담기 (물건을 쪼갤 수 있음)
- 주의: 물건을 쪼갤 수 없는 배낭문제(0-1 배낭문제)는 그리디로 풀 수 없음!
배낭 용량: 50kg
물건 (무게, 가치):
A: 10kg, $60 → 가치/무게 = $6/kg
B: 20kg, $100 → 가치/무게 = $5/kg
C: 30kg, $120 → 가치/무게 = $4/kg
목표: 최대 가치그리디 접근
전략: 가치/무게 비율이 높은 것부터 담기
def fractional_knapsack(capacity, items):
"""
분할 가능 배낭 문제
그리디 전략: 가치 밀도(가치/무게) 높은 순
capacity: 배낭 용량 (예: 50kg)
items: [(무게, 가치), ...] 리스트 * 예: [(10, 60), (20, 100), (30, 120)]
Returns: (최대 가치, 선택 내역)
핵심 아이디어:
- 1kg당 가치가 높은 물건부터 담기
- 물건을 쪼갤 수 있으므로 일부만 담을 수도 있음
"""
# 1. 각 물건의 가치 밀도(가치/무게) 계산
items_with_ratio = []
for weight, value in items:
ratio = value / weight # 가치 밀도 = 1kg당 가치 *예: 10kg에 60달러 → 6달러/kg
items_with_ratio.append((ratio, weight, value)) # (가치밀도, 무게, 가치) 튜플로 저장
# 나중에 정렬하기 위해 ratio를 맨 앞에
# 2. 가치 밀도가 높은 순으로 정렬
items_with_ratio.sort(reverse=True) # reverse=True: 내림차순 (큰 것부터)
# 예: [(6, 10, 60), (5, 20, 100), (4, 30, 120)]
total_value = 0 # 담은 물건의 총 가치
selections = [] # 어떤 물건을 얼마나 담았는지 기록하기 위한 리스트
# 3. 가치 밀도가 높은 물건부터 배낭에 담기
for ratio, weight, value in items_with_ratio:
# 경우 1: 물건 전체를 담을 수 있는 경우
if capacity >= weight:
# 물건 전체를 배낭에 담음
capacity -= weight # 남은 용량 감소
total_value += value # 가치 추가
selections.append((weight, value, 1.0)) # 기록: (무게, 가치, 담은 비율)
# 1.0 = 100% 전체를 담음
# 경우 2: 물건 일부만 담을 수 있는 경우
else:
# 남은 용량만큼만 담기
fraction = capacity / weight # fraction = 담을 수 있는 비율
# 예: 30kg 물건인데 20kg만 남음 → 20/30 = 0.667
total_value += value * fraction # 일부만 담으므로 가치도 비율만큼만
# 예: 120달러 물건의 66.7% → 80달러
# 기록
selections.append((weight, value, fraction))
break # 배낭이 가득 찼으므로 더 이상 담을 수 없음
return total_value, selections
# 사용 예시
items = [
(10, 60), # A: 10kg, $60 → $6/kg
(20, 100), # B: 20kg, $100 → $5/kg
(30, 120), # C: 30kg, $120 → $4/kg
]
max_value, selected = fractional_knapsack(50, items)
print(f"최대 가치: ${max_value}") # 최대 가치: $240
print("선택 내역:")
for weight, value, fraction in selected:
actual_weight = weight * fraction # 실제 담은 무게
actual_value = value * fraction # 실제 얻은 가치
print(f" 무게 {weight}kg 중 {actual_weight:.1f}kg 담음 → ${actual_value:.0f}")
# 출력:
# 무게 10kg 중 10.0kg 담음 → $60 (A 전체)
# 무게 20kg 중 20.0kg 담음 → $100 (B 전체)
# 무게 30kg 중 20.0kg 담음 → $80 (C의 66.7%)
# 총 50kg, $240🔢 최소 신장 트리(Minimum Spanning Tree, MST) - 크루스칼 알고리즘(Kruskal Algorithm)
크루스칼 알고리즘은 그래프에서 간선을 하나씩 추가하면서 최소 신장 트리를 만드는 방식의 알고리즘입니다.
그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용됩니다.
즉, 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때,
가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용하게 됩니다.
문제 설명
최소 신장 트리(MST): 모든 정점을 연결하되, 간선 가중치 합이 최소, 사이클 없음
그래프:
A
/|\
1 2 3
/ | \
B---4---C
|
5
|
D
목표: 모든 정점을 최소 비용으로 연결크루스칼 알고리즘
그리디 전략: 가장 작은 간선부터 선택 (사이클 방지)
class UnionFind:
"""
Union-Find 자료구조 (사이클 탐지용)
목적: 그래프에서 두 정점이 같은 그룹인지 빠르게 확인
활용: 간선을 추가할 때 사이클이 생기는지 확인
"""
def __init__(self, n):
"""
n개의 정점 초기화
n: 정점 개수
"""
self.parent = list(range(n)) # parent[i]: i번 정점의 부모
# 초기에는 자기 자신이 부모 (각자 독립된 그룹)
# 예: n=4 → [0, 1, 2, 3]
self.rank = [0] * n # rank[i]: i를 루트로 하는 트리의 높이 (근사값)
# Union by Rank 최적화에 사용
def find(self, x):
"""
x가 속한 그룹의 대표(루트) 찾기
경로 압축 최적화 적용:
- 찾는 과정에서 만난 모든 노드를 루트에 직접 연결
- 다음 find 호출 시 O(1)에 가까워짐
x: 찾을 정점
Returns: x가 속한 그룹의 대표 정점
"""
# x의 부모가 자기 자신이면 → x가 루트
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 재귀로 루트를 찾으면서 경로 압축:
# x의 부모를 루트로 직접 연결
return self.parent[x]
def union(self, x, y):
"""
x와 y가 속한 두 그룹을 하나로 합치기
Union by Rank 최적화:
- 작은 트리를 큰 트리 아래에 붙임
- 트리의 높이가 커지는 것을 방지
x, y: 합칠 두 정점
Returns: bool: 합치기 성공 여부
True: 서로 다른 그룹이었음 (합침)
False: 이미 같은 그룹 (사이클!)
"""
# 각 정점의 루트 찾기
root_x = self.find(x)
root_y = self.find(y)
# 이미 같은 그룹이면
if root_x == root_y:
return False # 합칠 수 없음 (사이클 발생!)
# Union by Rank: 작은 트리를 큰 트리 아래에
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y # x 트리가 더 작음 → y 아래에 붙임
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x # y 트리가 더 작음 → x 아래에 붙임
else:
self.parent[root_y] = root_x # 높이가 같으면 아무거나 아래에 붙이고
self.rank[root_x] += 1 # 새로운 루트의 높이 1 증가
return True # 합치기 성공
def kruskal_mst(n, edges):
"""
크루스칼 알고리즘 - 최소 신장 트리 (MST)
목표: n개의 정점을 모두 연결하되, 간선 가중치 합이 최소
그리디 전략:
1. 가장 작은 가중치의 간선부터 선택
2. 사이클이 생기지 않는 간선만 선택
3. n-1개의 간선을 선택하면 완성
n: 정점 개수
edges: [(가중치, u, v), ...] 간선 리스트(정점 u, v 사이 가중치) * 예: [(1, 0, 1), (2, 0, 2), ...]
Returns: (MST 간선 리스트, 총 비용)
시간복잡도: O(E log E) - 간선 정렬이 지배
"""
# 1. 가장 작은 가중치부터 선택하기 위해 간선을 가중치 순으로 정렬 (오름차순)
edges.sort() # 예: [(1,0,1), (2,0,2), (3,0,2), (4,1,2), (5,2,3)]
uf = UnionFind(n) # Union-Find 초기화, 사이클 탐지에 사용
mst = [] # 선택된 MST 간선들
total_cost = 0 # MST의 총 가중치
# 2. 작은 간선부터 하나씩 확인
for weight, u, v in edges:
# 3. u와 v를 연결해도 사이클이 생기지 않는지 확인
# union이 True를 반환 → 서로 다른 그룹 → 사이클 없음
# union이 False를 반환 → 이미 같은 그룹 → 사이클 생김
if uf.union(u, v):
mst.append((u, v, weight)) # 사이클이 없으므로 이 간선 선택
total_cost += weight
# 4. MST는 정확히 n-1개의 간선 필요
if len(mst) == n - 1: # n-1개를 선택했으면 완성!
break
return mst, total_cost
# 사용 예시
# 정점: 0(A), 1(B), 2(C), 3(D)
edges = [
(1, 0, 1), # A-B: 가중치 1
(2, 0, 2), # A-C: 가중치 2
(3, 0, 2), # A-C: 가중치 3 (중복 간선, 더 무거움)
(4, 1, 2), # B-C: 가중치 4
(5, 2, 3), # C-D: 가중치 5
]
mst, cost = kruskal_mst(4, edges)
print("MST 간선:")
for u, v, weight in mst:
print(f" {u}-{v}: 가중치 {weight}")
# MST 간선:
# 0-1: 가중치 1
# 0-2: 가중치 2
# 2-3: 가중치 5
print(f"총 비용: {cost}") # 총 비용: 8
# 단계별 실행 과정:
#
# 정렬 후: [(1,0,1), (2,0,2), (3,0,2), (4,1,2), (5,2,3)]
#
# 1. (1,0,1) - A와 B 연결
# 그룹: {A,B}, {C}, {D}
# 사이클? 없음 → 선택 ✓
# MST: [(0,1,1)], 비용: 1
#
# 2. (2,0,2) - A와 C 연결
# 그룹: {A,B,C}, {D}
# 사이클? 없음 → 선택 ✓
# MST: [(0,1,1), (0,2,2)], 비용: 3
#
# 3. (3,0,2) - A와 C 연결 시도
# 그룹: {A,B,C}, {D}
# 사이클? A와 C 이미 연결됨 → 건너뛰기 ✗
#
# 4. (4,1,2) - B와 C 연결 시도
# 그룹: {A,B,C}, {D}
# 사이클? B와 C 이미 연결됨 → 건너뛰기 ✗
#
# 5. (5,2,3) - C와 D 연결
# 그룹: {A,B,C,D}
# 사이클? 없음 → 선택 ✓
# MST: [(0,1,1), (0,2,2), (2,3,5)], 비용: 8
# 3개 간선 완성! (n-1 = 4-1 = 3)📊 허프만 코딩 (Huffman coding)
허프만 코딩이란?
허프만 코딩(Huffman Coding)은 데이터를 압축하는 알고리즘입니다.
자주 나오는 문자에는 짧은 코드를, 드물게 나오는 문자에는 긴 코드를 부여하여 전체 데이터 크기를 줄입니다.
실생활 비유:
택배 상자 포장:
자주 보내는 물건 (스마트폰) → 전용 박스 준비 (빠름, 효율적)
가끔 보내는 물건 (이상한 모양) → 맞춤 포장 필요 (느림, 복잡)
자주 쓰는 것을 간단하게!왜 허프만 코딩이 필요한가?
문제: 고정 길이 인코딩의 비효율
일반적인 텍스트 저장 방식은 모든 문자에 같은 비트 수를 사용합니다.
문자열: "AAAAABBBCCDE"
ASCII 코딩 (고정 길이): 모든 문자 = 8비트
- A: 01000001 (8비트)
- B: 01000010 (8비트)
- C: 01000011 (8비트)
- D: 01000100 (8비트)
- E: 01000101 (8비트)
총 크기: 12문자 × 8비트 = 96비트문제점: A는 5번 나오는데, D는 1번만 나옵니다. 똑같이 8비트를 쓰는 게 비효율적입니다!
해결책: 가변 길이 인코딩
자주 나오는 문자 → 짧은 코드
드물게 나오는 문자 → 긴 코드
- A (5번): 0 (1비트)
- B (3번): 10 (2비트)
- C (2번): 110 (3비트)
- D (1번): 1110 (4비트)
- E (1번): 1111 (4비트)
총 크기: 5×1 + 3×2 + 2×3 + 1×4 + 1×4
= 5 + 6 + 6 + 4 + 4 = 25비트
96비트 → 25비트 (74% 압축!)허프만 코딩의 핵심 원리
1. 빈도수 기반
문자가 얼마나 자주 나오는지가 핵심입니다.
문자열: "AAAAABBBCCDE"
빈도 계산:
A: █████ (5번)
B: ███ (3번)
C: ██ (2번)
D: █ (1번)
E: █ (1번)
규칙: 빈도 높음 → 코드 짧게
빈도 낮음 → 코드 길게2. 이진 트리 구조
허프만 코딩은 이진 트리를 만들어서 코드를 생성합니다.
트리의 규칙:
- 왼쪽으로 가면 '0'
- 오른쪽으로 가면 '1'
- 리프(끝)에 실제 문자
예시:
(루트)
0/ \1
/ \
A (중간)
/ \
0/ \1
/ \
B (중간)
/ \
0/ \1
/ \
C (중간)
/ \
0/ \1
/ \
D E
A까지 경로: 0 → 코드 '0'
B까지 경로: 1, 0 → 코드 '10'
C까지 경로: 1, 1, 0 → 코드 '110'
D까지 경로: 1, 1, 1, 0 → 코드 '1110'
E까지 경로: 1, 1, 1, 1 → 코드 '1111'허프만 트리 만들기 (단계별)
초기 상태: 각 문자를 개별 노드로
문자열: "AAAAABBBCCDE"
5개 노드(문자:빈도): [D:1] [E:1] [C:2] [B:3] [A:5]규칙: 빈도가 가장 낮은 2개를 합친다!
1단계: D(1)와 E(1) 합치기
가장 작은 2개: D(1), E(1)
합치기:
(2) ← 새 노드 (1+1=2)
/ \
D(1) E(1)
남은 노드: [DE:2] [C:2] [B:3] [A:5]2단계: DE(2)와 C(2) 합치기
가장 작은 2개: DE(2), C(2)
합치기:
(4) ← 새 노드 (2+2=4)
/ \
(2) C(2)
/ \
D(1) E(1)
남은 노드: [DEC:4] [B:3] [A:5]3단계: B(3)와 DEC(4) 합치기
가장 작은 2개: B(3), DEC(4)
합치기:
(7) ← 새 노드 (3+4=7)
/ \
B(3) (4)
/ \
(2) C(2)
/ \
D(1) E(1)
남은 노드: [BDEC:7] [A:5]4단계: A(5)와 BDEC(7) 합치기
마지막 2개: A(5), BDEC(7)
합치기:
(12) ← 루트 (5+7=12)
/ \
A(5) (7)
/ \
B(3) (4)
/ \
(2) C(2)
/ \
D(1) E(1)
완성!코드 추출하기
규칙:
- 왼쪽 = 0
- 오른쪽 = 1
- 루트에서 리프까지의 경로(각 경로는 0, 1로 표시) = 코드
완성된 트리:
(12)
/ \
0/ \1
/ \
A(5) (7)
/ \
0/ \1
/ \
B(3) (4)
/ \
0/ \1
/ \
(2) C(2)
/ \
0/ \1
/ \
D(1) E(1)
A: 루트 → 왼쪽(0) = '0'
B: 루트 → 오른쪽(1) → 왼쪽(0) = '10'
C: 루트 → 오른쪽(1) → 오른쪽(1) → 오른쪽(1) = '111'
D: 루트 → 오른쪽(1) → 오른쪽(1) → 왼쪽(0) → 왼쪽(0) = '1100'
E: 루트 → 오른쪽(1) → 오른쪽(1) → 왼쪽(0) → 오른쪽(1) = '1101'결과:
문자 빈도 코드 비트수
A 5 0 1
B 3 10 2
C 2 111 3
D 1 1100 4
E 1 1101 4압축 예시
원본 문자열: "AAAAABBBCCDE"
압축 과정:
A A A A A B B B C C D E
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
0 0 0 0 0 10 10 10 111 111 1100 1101
= 0000010101011111111001101
총 25비트원본과 비교:
고정 길이 (최소 3비트/문자): A(000), B(001), C(010), D(011), E(100)
12문자 × 3비트 = 36비트
허프만 코딩:
25비트
절약: 36 - 25 = 11비트 (31% 압축)디코딩 (압축 풀기)
압축된 데이터를 다시 원본으로 복원합니다.
압축 데이터: 00000101010110110111011111
허프만 트리: 위에서 만든 트리 사용
디코딩 과정:
1. 루트에서 시작
2. 0이면 왼쪽, 1이면 오른쪽
3. 리프 도달하면 문자 출력, 다시 루트로
비트열: 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 1
0 → 왼쪽 → 0 : A ✓ (루트로)
0 → 왼쪽 → 0 : A ✓ (루트로)
0 → 왼쪽 → 0 : A ✓ (루트로)
0 → 왼쪽 → 0 : A ✓ (루트로)
0 → 왼쪽 → 0 : A ✓ (루트로)
1 → 오른쪽 → 1
0 → 왼쪽 → 10 : B ✓ (루트로)
1 → 오른쪽 → 1
0 → 왼쪽 → 10 : B ✓ (루트로)
1 → 오른쪽 → 1
0 → 왼쪽 → 10 : B ✓ (루트로)
1 → 오른쪽 → 1
1 → 오른쪽 → 11
1 → 오른쪽 → 111 : C ✓ (루트로)
... (계속)
결과: AAAAABBBCCDE중요: 허프만 코드는 접두어가 없습니다(prefix-free).
접두어가 없다는 말은 어떤 문자의 이진 코드가 다른 문자의 이진 코드의 '앞부분(접두어)'이 되지 않는다는 뜻입니다. 즉, 어떤 코드도 다른 코드의 시작 부분이 아닙니다.
쉽게 말해, 코드를 읽다가 "어? 이거 A네!"라고 판단되는 순간, 그 뒤에 나오는 비트들은 무조건 다음 문자의 것이라는 확신을 가질 수 있다는 의미입니다.
A: 0
B: 10
C: 110
'0'은 '10'이나 '110'의 접두어가 아님
'10'은 '110'의 접두어가 아님
→ 비트열을 순서대로 읽으면 유일하게 해석됨 → 구분자 없이도 디코딩 가능!허프먼 코딩에서 heap을 쓰는 이유
허프만 알고리즘의 핵심은 "빈도수가 가장 낮은 두 노드를 계속 합치는 것입니다.
데이터를 정렬된 상태로 유지하면서 계속 넣고 빼야 하는데, 이때 최소 힙(Min-Heap)을 쓰면
항상 가장 빈도가 낮은 노드를 O(log N)의 속도로 빠르게 찾아낼 수 있습니다.
구현 코드 (상세 주석)
import heapq
class HuffmanNode:
"""허프만 트리의 노드"""
def __init__(self, char, freq):
self.char = char # 문자 (리프 노드만)
self.freq = freq # 빈도
self.left = None # 왼쪽 자식
self.right = None # 오른쪽 자식
def __lt__(self, other): # __lt__ (Less Than): HuffmanNode 클래스 안에 노드끼리 크기를 비교
"""우선순위 큐용: 빈도가 작은 것이 우선"""
return self.freq < other.freq
def huffman_coding(text):
"""허프만 코딩"""
# ===== 1단계: 빈도 계산 =====
freq_map = {} # 빈도를 저장할 딕셔너리(key:value 형태)
for char in text: # text 에서 문자를 하나씩 순서대로 꺼냄
freq_map[char] = freq_map.get(char, 0) + 1
# freq_map.get(char, 0): freq_map 딕셔너리에 'char' key가 있으면 해당하는 value(빈도 수), 없으면 0 반환
# 예: text = "AAAAABBBCCDE"
# 최종 freq_map = {'A':5, 'B':3, 'C':2, 'D':1, 'E':1}
print("1단계: 빈도 계산")
for char, freq in sorted(freq_map.items()):
print(f" {char}: {'█' * freq} ({freq}번)") # 문자별 빈도 수를 '█' 수로 표시
print()
# ===== 2단계: 우선순위 큐 초기화 =====
# 노드 생성 및 힙에 삽입
heap = []
for char, freq in freq_map.items(): # 딕셔너리에서 (문자, 빈도수) 쌍을 하나씩 가져옴
node = HuffmanNode(char, freq) # HuffmanNode: 트리 구조를 만들기 위한 전용 객체로 각 문자, 빈도수를 담은 객체 생성
heapq.heappush(heap, node) # 생성된 노드를 힙(heap)에 저장
# 이때 빈도수가 가장 낮은 노드가 항상 맨 앞(루트)에 오도록 자동으로 정렬
print("2단계: 초기 노드")
# 현재 힙 상태 확인 (디버깅용 출력 코드)
temp = []
while heap:
node = heapq.heappop(heap) # 빈도수가 가장 낮은 노드를 하나씩 꺼냄
print(f" [{node.char}:{node.freq}]", end=" ")
temp.append(node)
for node in temp: # 앞에서 출력하려고 노드를 다 꺼냈기 때문에, 실제 허프만 트리를 만들기 위해 다시 힙에 집어넣는 과정
heapq.heappush(heap, node)
print("\n")
# ===== 3단계: 허프만 트리 구성 =====
print("3단계: 트리 구성") # 빈도수가 낮은 노드들을 하단에서부터 차례로 묶어 올라가며 하나의 거대한 트리를 만드는 과정
step = 1
while len(heap) > 1: # 힙에 노드가 하나만 남을 때까지 계속 반복, 마지막에 남는 노드가 바로 전체 트리의 뿌리(Root)가 됨
left = heapq.heappop(heap) # 빈도 수가 가장 작은 2개 노드 꺼내기
right = heapq.heappop(heap)
print(f" 단계 {step}: [{left.char or ''}:{left.freq}]와 "
f"[{right.char or ''}:{right.freq}] 합치기 "
f"→ [{left.freq + right.freq}]")
# 꺼낸 두 노드를 자식으로 갖는 부모 노드를 만듬
merged = HuffmanNode(None, left.freq + right.freq) # char: 이 부모 노드는 char를 직접 담지 않으므로 None
# freq: 왼쪽과 오른쪽 자식의 빈도수를 더한 값으로 이 노드의 무게가 됨
merged.left = left # 새로 만든 부모 노드 밑에 앞에서 꺼낸 두 노드를 연결, 이 연결 과정을 통해 트리가 위로 쌓여 올라감
merged.right = right
heapq.heappush(heap, merged) # 합쳐진 새 노드를 다시 힙에 넣음. 이 합쳐진 덩어리는 다른 노드와 또 합쳐질 준비를 함
step += 1 # 이렇게 빈도가 낮은 것부터 묶어 올라가면,
# 빈도가 낮은 문자는 트리에서 멀리(코드가 길어짐) 위치하게 되고,
# 빈도가 높은 문자는 트리의 상단(코드가 짧아짐)에 위치하게 됨
print()
# ===== 4단계: 코드 추출 =====
root = heap[0] # 전체 트리의 뿌리(최상단 노드)로 여기서부터 탐색을 시작
codes = {} # 결과물(예: {'A': '0', 'B': '10'})을 저장할 빈 딕셔너리
def build_codes(node, code):
"""재귀로 코드 생성"""
if node.char is not None:
# 리프 노드(Leaf Node, 문자 있음): 코드 저장
codes[node.char] = code
else:
# 내부 노드(Internal Node, 문자 없음): 계속 탐색
if node.left:
build_codes(node.left, code + '0') # 왼쪽으로 갈 때는 기존 코드 뒤에 '0'을 붙임
if node.right:
build_codes(node.right, code + '1') # 오른쪽으로 갈 때는 기존 코드 뒤에 '1'을 붙임
build_codes(root, '')
print("4단계: 코드 추출")
print(f" {'문자':<6} {'빈도':<6} {'코드':<8} {'총 비트'}") # '문자':<6 -> '문자' 글자를 포함 총 6칸을 잡고 왼쪽 정렬
print(" " + "-" * 35)
total_bits = 0
for char in sorted(codes.keys()):
freq = freq_map[char]
code = codes[char]
bits = freq * len(code)
total_bits += bits
print(f" {char:<6} {freq:<6} {code:<8} {bits}")
print(f"\n총 {total_bits}비트")
print(f"고정 길이 (3비트): {len(text) * 3}비트")
print(f"압축률: {(1 - total_bits/(len(text)*3))*100:.1f}%")
return codes
# 실행
text = "AAAAABBBCCDE"
print(f"원본 문자열: \"{text}\"\n")
codes = huffman_coding(text)실행 결과:
원본 문자열: "AAAAABBBCCDE"
1단계: 빈도 계산
A: █████ (5번)
B: ███ (3번)
C: ██ (2번)
D: █ (1번)
E: █ (1번)
2단계: 초기 노드
[D:1] [E:1] [C:2] [B:3] [A:5]
3단계: 트리 구성
단계 1: [D:1]와 [E:1] 합치기 → [2]
단계 2: [C:2]와 [:2] 합치기 → [4]
단계 3: [B:3]와 [:4] 합치기 → [7]
단계 4: [A:5]와 [:7] 합치기 → [12]
4단계: 코드 추출
문자 빈도 코드 총 비트
-----------------------------------
A 5 0 5
B 3 10 6
C 2 110 6
D 1 1110 4
E 1 1111 4
총 25비트
고정 길이 (3비트): 36비트
압축률: 30.6%허프만 코딩의 활용
1. 파일 압축
ZIP, GZIP 등의 압축 프로그램 → 내부적으로 허프만 코딩 사용2. 이미지 압축
JPEG 압축의 일부 → 빈도 높은 색상에 짧은 코드3. 통신
데이터 전송 시 대역폭 절약 → 모뎀, 팩스 등허프만 코딩의 장단점
장점:
- ✅ 최적 압축 보장 (같은 조건에서)
- ✅ 손실 없는 압축
- ✅ 구현이 비교적 간단
단점:
- ⚠️ 트리를 함께 저장해야 함 (오버헤드)
- ⚠️ 파일이 작으면 오히려 커질 수 있음
- ⚠️ 적응형 압축 불가 (사전에 빈도 알아야 함)
💡 실무 팁
그리디를 사용할 수 있는 조건
-
탐욕 선택 속성(Greedy Choice Property)
- 지역 최적 선택이 전역 최적으로 이어짐
-
최적 부분 구조(Optimal Substructure)
- 부분 문제의 최적해가 전체 최적해에 포함됨
그리디 증명 방법
1. 귀류법: 그리디가 아닌 해가 더 좋다고 가정 → 모순 도출
2. 교환 논증: 최적해를 그리디로 바꿔도 여전히 최적임을 증명
3. 수학적 귀납법: 각 단계에서 최적임을 증명그리디 vs 동적 계획법
그리디:
- 한 번 선택하면 번복 안함
- 빠름 O(n log n) 이하
- 항상 최적 보장 ✗
동적 계획법:
- 모든 경우 고려 후 선택
- 느림 O(n²) 이상
- 최적 보장 ✓
예: 0-1 배낭문제에서 그리디는 안되지만 DP는 가능디버깅 팁
- 작은 예제로 검증
- 반례를 찾아보기
- 정렬 순서가 올바른지 확인
- 최적성 증명 시도
🎯 핵심 정리
그리디의 본질
- 매 순간 가장 좋은 선택
- 한 번 선택하면 번복 없음
- 직관적이고 빠름
주요 알고리즘
문제 전략 시간복잡도
----------------------------------------------------------
거스름돈 큰 동전 먼저 O(k) k=동전 종류
회의실 배정 빨리 끝나는 것 O(n log n)
분할 가능 배낭 가치/무게 높은 것 O(n log n)
MST (크루스칼) 작은 간선부터 O(E log E)
허프만 코딩 빈도 낮은 것 합치기 O(n log n)그리디 판별법
1. 정렬이 필요한가? → 그리디 가능성 높음
2. "가장 ~한 것"을 선택? → 그리디
3. 선택 후 번복 없음? → 그리디
4. 반례가 있는가? → 그리디 불가주의사항
- 항상 최적해를 보장하지 않음
- 증명 없이 사용하면 위험
- 반례를 찾아보는 습관
🔗 다음 글에서는
[06-04] 동적 계획법 (Dynamic Programming)
- 동적 계획법의 개념: 중복되는 부분 문제를 저장하여 효율적으로 해결
- 피보나치 수열: DP의 가장 기본적인 예시와 메모이제이션
- 최장 공통 부분 수열(LCS): 2차원 DP 테이블을 활용한 문자열 문제
- 0-1 배낭 문제: 그리디로 풀 수 없는 문제를 DP로 해결하기
이전 글: [06-02] 분할 정복
다음 글: [06-04] 동적 계획법
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자