개념
매 순간 최선의 선택을 하는 알고리즘
현재 상황에서 가장 좋아 보이는 것을 선택 (지역 최적해 → 전역 최적해)
시간복잡도
| 문제 유형 | 시간복잡도 |
|---|---|
| 정렬 기반 | O(n log n) |
| 단순 선택 | O(n) |
| 우선순위 큐 | O(n log n) |
특징
그리디가 적용되는 조건
-
탐욕적 선택 속성 (Greedy Choice Property)
- 각 단계의 최선 선택이 전체 최적해로 이어짐
-
최적 부분 구조 (Optimal Substructure)
- 부분 문제의 최적해가 전체 최적해에 포함됨
장점
- 빠른 속도: 대부분 O(n) ~ O(n log n)
- 구현 간단: 직관적이고 이해하기 쉬움
단점
- 최적해 보장 안 됨: 모든 문제에 적용 불가
- 증명 필요: 그리디가 최적해를 보장하는지 증명 필요
구현 방법
기본 패턴
def greedy(items):
# 1. 정렬 (필요시)
items.sort(key=lambda x: criterion(x))
result = 0
# 2. 각 단계에서 최선 선택
for item in items:
if is_valid(item):
result += item
return result자주 나오는 문제 유형
1. 동전 거스름돈
문제: 거스름돈을 가장 적은 동전으로 만들기
def coin_change_greedy(amount, coins):
coins.sort(reverse=True) # 큰 동전부터
count = 0
for coin in coins:
count += amount // coin
amount %= coin
return count if amount == 0 else -1
# 테스트 (단, 동전이 배수 관계일 때만 최적해 보장)
print(coin_change_greedy(1260, [500, 100, 50, 10])) # 6
# 시간복잡도: O(n log n)주의: 동전이 배수 관계가 아니면 DP 사용 필요
2. 회의실 배정
문제: 최대한 많은 회의를 배정
def max_meetings(meetings):
# 종료 시간 기준 정렬
meetings.sort(key=lambda x: x[1])
count = 0
end_time = 0
for start, end in meetings:
if start >= end_time:
count += 1
end_time = end
return count
# 테스트
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
print(max_meetings(meetings)) # 4
# 시간복잡도: O(n log n)핵심: 종료 시간이 빠른 회의부터 선택
3. ATM 대기 시간
문제: 각 사람이 돈을 인출하는데 걸리는 시간의 합 최소화
def min_waiting_time(times):
times.sort()
total = 0
waiting = 0
for time in times:
waiting += time
total += waiting
return total
# 테스트
print(min_waiting_time([3, 1, 4, 3, 2])) # 32
# 시간복잡도: O(n log n)핵심: 시간이 짧은 사람부터 처리
4. 큰 수 만들기
문제: 숫자에서 k개를 제거하여 가장 큰 수 만들기
def remove_k_digits(num, k):
stack = []
for digit in num:
# 현재 숫자가 스택 top보다 크면 제거
while stack and k > 0 and stack[-1] < digit:
stack.pop()
k -= 1
stack.append(digit)
# 남은 k개 제거 (뒤에서부터)
if k > 0:
stack = stack[:-k]
# 결과 생성
result = ''.join(stack).lstrip('0')
return result if result else '0'
# 테스트
print(remove_k_digits("1924", 2)) # "94"
print(remove_k_digits("4177252841", 4)) # "775841"
# 시간복잡도: O(n)핵심: 스택을 이용해 작은 숫자 제거
5. 섬 연결하기 (최소 신장 트리 - 크루스칼)
문제: 모든 섬을 연결하는 최소 비용
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
def min_cost_connect(n, costs):
# 비용 기준 정렬
costs.sort(key=lambda x: x[2])
parent = [i for i in range(n)]
total_cost = 0
edges = 0
for a, b, cost in costs:
# 사이클이 생기지 않으면 연결
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
total_cost += cost
edges += 1
if edges == n - 1:
break
return total_cost
# 테스트
costs = [[0,1,1], [0,2,2], [1,2,5], [1,3,1], [2,3,8]]
print(min_cost_connect(4, costs)) # 4
# 시간복잡도: O(E log E)핵심: 비용이 작은 간선부터 선택 (Union-Find 사용)
6. 체육복
문제: 여벌 체육복을 빌려주어 최대한 많은 학생이 체육 수업 참여
def solution(n, lost, reserve):
# 여벌이 있지만 도난당한 경우 제외
lost_only = set(lost) - set(reserve)
reserve_only = set(reserve) - set(lost)
# 앞뒤 학생에게 빌려주기
for r in sorted(reserve_only):
if r - 1 in lost_only:
lost_only.remove(r - 1)
elif r + 1 in lost_only:
lost_only.remove(r + 1)
return n - len(lost_only)
# 테스트
print(solution(5, [2, 4], [1, 3, 5])) # 5
# 시간복잡도: O(n log n)핵심: 정렬 후 가까운 번호부터 빌려주기
추천 연습 문제
기초
중급
고급
핵심 요약
| 개념 | 설명 |
|---|---|
| 원리 | 매 순간 최선의 선택 |
| 조건 | 탐욕적 선택 속성, 최적 부분 구조 |
| 시간복잡도 | 주로 O(n log n) (정렬) |
| 활용 | 최적화 문제, 스케줄링 |
그리디 알고리즘 템플릿
1. 정렬 기반
def greedy_sort(items):
# 기준에 따라 정렬
items.sort(key=lambda x: x.criterion)
result = 0
for item in items:
if can_select(item):
result += process(item)
return result2. 우선순위 큐 기반
import heapq
def greedy_heap(items):
heap = []
for item in items:
heapq.heappush(heap, item)
result = 0
while heap:
best = heapq.heappop(heap)
result += process(best)
return result3. 투 포인터 기반
def greedy_two_pointer(items):
left, right = 0, len(items) - 1
result = 0
while left < right:
if condition(items[left], items[right]):
result += process(left, right)
left += 1
else:
right -= 1
return resultDP vs 그리디
| 특성 | DP | 그리디 |
|---|---|---|
| 접근 | 모든 경우 고려 | 현재 최선만 선택 |
| 최적해 | 항상 보장 | 문제에 따라 다름 |
| 시간복잡도 | 느림 (다항 시간) | 빠름 (선형~로그) |
| 메모리 | 많이 사용 | 적게 사용 |
| 예시 | 배낭 문제 | 회의실 배정 |
주의사항
1. 최적해 보장 확인
# 그리디로 풀기 전에 반례 찾기
# 예: 동전 [1, 3, 4]로 6 만들기
# 그리디: 4 + 1 + 1 = 3개
# 최적해: 3 + 3 = 2개2. 정렬 기준
# 잘못된 기준
items.sort(key=lambda x: x[0])
# 올바른 기준 (문제에 따라)
items.sort(key=lambda x: x[1])
items.sort(key=lambda x: (x[1], x[0]))3. 증명 방법
# 1. 교환 논증 (Exchange Argument)
# - 그리디 선택을 다른 선택으로 바꾸면 손해
# 2. 귀류법 (Proof by Contradiction)
# - 그리디가 최적이 아니라고 가정하고 모순 도출그리디 문제 판별법
그리디로 풀 수 있는 신호
- “최대한 많이”, “최소 비용”
- 정렬하면 해결될 것 같음
- 각 단계의 선택이 명확함
- 반례가 없음
DP가 필요한 신호
- 모든 경우를 고려해야 함
- 그리디 반례가 존재
- 중복되는 부분 문제
- “경우의 수” 문제
그리디 최적화 기법
1. 정렬 최적화
# 여러 기준으로 정렬
items.sort(key=lambda x: (x[0], -x[1]))2. 우선순위 큐
import heapq
# 최솟값 빠르게 찾기
heap = []
heapq.heappush(heap, value)
min_val = heapq.heappop(heap)3. Union-Find
# 사이클 탐지 (크루스칼 알고리즘)
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]그리디 전략
1. 최소 선택
- 가장 작은 것부터
- 예: ATM, 동전
2. 최대 선택
- 가장 큰 것부터
- 예: 큰 수 만들기
3. 빠른 종료
- 끝나는 시간이 빠른 것
- 예: 회의실 배정
4. 비율 최대화
- 가치/무게 비율
- 예: 분수 배낭 문제