[Daily morning study] 그리디 알고리즘 개념과 예시
#daily morning study
그리디 알고리즘이란?
그리디(Greedy) 알고리즘은 매 선택 단계에서 현재 상태 기준으로 가장 최선의 선택을 반복해서 문제를 푸는 방식이다. 전체적인 최적해를 한 번에 계산하지 않고, 지금 당장 가장 좋아 보이는 것만 고른다.
핵심 특징:
- 탐욕적 선택: 현재 상태에서 최선의 옵션을 고른다
- 비가역적 선택: 한 번 선택한 건 번복하지 않는다
- 모든 문제에 적용 가능하지 않다
그리디가 성립하는 조건
다음 두 가지 성질이 동시에 만족될 때만 그리디가 최적해를 보장한다.
탐욕 선택 속성 (Greedy Choice Property)
지역적으로 최선인 선택이 전역 최적해로 이어진다.최적 부분 구조 (Optimal Substructure)
문제의 최적해가 부분 문제의 최적해들로 구성된다.
두 조건이 성립하지 않으면 그리디는 틀린 답을 낼 수 있다. 그럴 땐 DP나 완전 탐색으로 전환해야 한다.
대표 예시
1. 거스름돈 문제
동전 종류가 500, 100, 50, 10원일 때 가장 적은 동전 개수로 거슬러주기.
def greedy_change(amount):
coins = [500, 100, 50, 10]
count = 0
for coin in coins:
count += amount // coin
amount %= coin
return count
print(greedy_change(1260)) # 6개 (500×2, 100×2, 50×1, 10×1)
이 문제에서 그리디가 성립하는 이유는 큰 단위 동전이 작은 단위 동전의 배수이기 때문이다.
동전 종류가 [500, 400, 100]처럼 배수 관계가 아니면 그리디가 실패한다.
- 800원을 거슬러줄 때:
- 그리디: 500 + 100 × 3 → 4개
- 최적: 400 × 2 → 2개
2. 활동 선택 문제 (Activity Selection)
겹치지 않게 가장 많은 활동을 선택하는 문제. 전략은 종료 시간이 빠른 활동부터 선택하는 것이다.
def activity_selection(activities):
# activities = [(start, end), ...]
activities.sort(key=lambda x: x[1]) # 종료 시간 기준 정렬
selected = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
print(activity_selection(activities))
# [(1, 4), (5, 7), (8, 9)]
종료 시간 기준으로 정렬하는 이유: 빨리 끝나는 활동을 고를수록 이후에 선택 가능한 활동이 많아지기 때문이다.
3. 최소 신장 트리 - Kruskal 알고리즘
그래프에서 모든 노드를 연결하는 최소 비용 경로를 찾는 문제.
전략은 가중치가 작은 간선부터 추가하되, 사이클이 생기면 제외하는 것이다.
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, rank, x, y):
rx, ry = find(parent, x), find(parent, y)
if rank[rx] < rank[ry]:
rx, ry = ry, rx
parent[ry] = rx
if rank[rx] == rank[ry]:
rank[rx] += 1
def kruskal(n, edges):
edges.sort(key=lambda x: x[2]) # 가중치 기준 정렬
parent = list(range(n))
rank = [0] * n
mst_cost = 0
for u, v, w in edges:
if find(parent, u) != find(parent, v):
union(parent, rank, u, v)
mst_cost += w
return mst_cost
Union-Find 자료구조로 사이클 여부를 O(α(n)) 시간에 판단하므로, 전체 시간 복잡도는 정렬 때문에 O(E log E)가 된다.
4. 허프만 코딩 (Huffman Coding)
자주 등장하는 문자에 짧은 비트 코드를, 드문 문자에 긴 비트 코드를 부여해 압축 효율을 높이는 알고리즘.
전략은 빈도수가 낮은 두 노드를 반복해서 합치는 것이다.
import heapq
def huffman_codes(freq):
# (빈도, 문자) 형태로 min-heap 구성
heap = [[w, [c, ""]] for c, 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:], key=lambda p: len(p[1]))
freq = {'a': 45, 'b': 13, 'c': 12, 'd': 16, 'e': 9, 'f': 5}
for char, code in huffman_codes(freq):
print(f"{char}: {code}")
# a: 0, c: 100, b: 101, f: 1100, e: 1101, d: 111
빈도가 높은 a는 1비트, 빈도가 낮은 f, e는 4비트를 받는다.
그리디 vs 동적 프로그래밍
| 구분 | 그리디 | 동적 프로그래밍 |
|---|---|---|
| 선택 방식 | 현재 상태에서 최선 선택 | 모든 경우 탐색 후 최적 선택 |
| 선택 재고 여부 | 불가 | 가능 (부분 문제 재활용) |
| 시간 복잡도 | 일반적으로 빠름 | 상대적으로 느림 |
| 메모리 | 적게 사용 | 메모이제이션 테이블 필요 |
| 적용 가능 범위 | 탐욕 선택 속성이 성립하는 문제 | 더 넓은 범위의 최적화 문제 |
DP와 그리디 모두 최적 부분 구조를 필요로 하지만, 그리디는 추가로 탐욕 선택 속성도 필요하다.
그리디 접근 체크리스트
- 문제에서 최적 부분 구조가 있는지 확인한다.
- 탐욕 선택 속성이 성립하는지 직관적으로 검토한다.
- 선택 기준(정렬 기준 등)을 명확히 정의한다.
- 반례를 찾아서 그리디가 틀릴 수 있는지 검증한다.
- 반례가 있으면 DP나 완전 탐색으로 전환한다.
정리
그리디 알고리즘은 매 단계에서 지역적으로 최선인 선택을 반복해 전역 최적해를 구하는 방식이다. 구현이 단순하고 실행 속도가 빠르지만, 탐욕 선택 속성과 최적 부분 구조 두 조건이 모두 성립할 때만 정확한 답을 보장한다. 거스름돈, 활동 선택, Kruskal MST, 허프만 코딩이 대표적인 그리디 문제이고, 반례 검증을 통해 그리디 적용 가능 여부를 판단하는 습관이 중요하다.
