그리디 알고리즘 | "매 순간 최선" 탐욕 알고리즘 완벽 정리
이 글의 핵심
그리디 알고리즘은 매 단계에서 지역 최선을 고르는 전략으로, 조건이 맞으면 효율적으로 최적해를 얻을 수 있습니다. 이 글에서는 적용 조건, 대표 문제, 증명 없이 쓸 때의 위험, 시간·공간 복잡도 관점과 코딩 테스트 팁을 다룹니다.
들어가며
탐욕법은 구현은 쉬워 보여도 최적성이 맞는지 증명하지 않으면 잘못된 답을 낼 수 있습니다. 이 글에서는 전형적인 그리디 패턴을 익히고, 언제 DP나 다른 전략으로 넘어가야 하는지 감을 잡을 수 있습니다.
”매 순간 최선의 선택이 최적해?”
그리디 알고리즘은 매 순간 최선의 선택을 합니다. 항상 최적해를 보장하지는 않지만, 증명 가능한 경우 매우 효율적입니다.
1. 그리디 알고리즘이란?
개념
그리디(탐욕) 알고리즘은 현재 단계에서 보이는 지역 최선만 고릅니다. 아래는 큰 단위 동전부터 최대한 많이 쓰는 거스름돈 예시입니다. 단, 동전 액면가가 임의이면 그리디가 최소 개수를 보장하지 않을 수 있으므로, 문제에서 그리디가 성립하는지(교환·정렬 조건 등)를 확인해야 합니다.
# 예: 거스름돈 (500, 100, 50, 10원)
# 1260원 거슬러주기
coins = [500, 100, 50, 10]
change = 1260
count = 0
for coin in coins:
count += change // coin # 최대한 많이
change %= coin
print(count) # 6 (500*2 + 100*2 + 50*1 + 10*1)그리디 vs DP
| 특징 | 그리디 | DP |
|---|---|---|
| 선택 | 현재 최선 | 모든 경우 고려 |
| 시간복잡도 | O(n log n) | O(n²) ~ O(2ⁿ) |
| 최적해 보장 | X (증명 필요) | O |
| 구현 | 간단 | 복잡 |
2. 대표 문제
문제 1: 회의실 배정
def max_meetings(meetings):
"""
최대한 많은 회의 배정
[(시작, 끝), ...]
"""
# 끝나는 시간 기준 정렬
meetings.sort(key=lambda x: x[1])
count = 0
last_end = 0
for start, end in meetings:
if start >= last_end:
count += 1
last_end = end
return count
# 테스트
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
print(max_meetings(meetings)) # 4
# (1,4), (5,7), (5,9) 선택 불가 → (1,4), (5,7) 선택문제 2: 동전 거스름돈
def min_coins(coins, amount):
"""
최소 동전 개수
"""
coins.sort(reverse=True)
count = 0
for coin in coins:
if amount >= coin:
count += amount // coin
amount %= coin
return count if amount == 0 else -1
# 테스트
coins = [500, 100, 50, 10]
print(min_coins(coins, 1260)) # 6
# ❌ 그리디 실패 예
coins = [10, 7, 1]
amount = 14
# 그리디: 10 + 1 + 1 + 1 + 1 = 5개
# 최적: 7 + 7 = 2개 (DP 필요!)문제 3: 큰 수 만들기
def make_largest_number(number, k):
"""
숫자 k개를 제거해서 가장 큰 수 만들기
"1924", k=2 → "94"
"""
stack = []
removed = 0
for digit in number:
# 스택 top이 현재보다 작으면 제거
while stack and removed < k and stack[-1] < digit:
stack.pop()
removed += 1
stack.append(digit)
# 아직 k개 안 지웠으면 뒤에서 제거
return ''.join(stack[:len(stack) - (k - removed)])
# 테스트
print(make_largest_number("1924", 2)) # "94"
print(make_largest_number("1231234", 3)) # "3234"3. 그리디 증명
증명 방법
1) 교환 논법 (Exchange Argument)
"그리디 선택을 다른 선택으로 바꿔도 더 나아지지 않음"2) 귀류법 (Proof by Contradiction)
"그리디가 최적해가 아니라고 가정 → 모순 도출"예: 회의실 배정 증명
"끝나는 시간이 가장 빠른 회의를 선택하는 것이 최적"
증명:
- 다른 회의를 선택하면 끝나는 시간이 더 늦음
- 끝나는 시간이 늦으면 다음 회의 선택 폭이 줄어듦
- 따라서 끝나는 시간이 빠른 회의가 최적4. 실전 문제
문제 1: 체육복 (프로그래머스)
def solution(n, lost, reserve):
"""
체육복 빌려주기
"""
# 여벌 있는데 도난당한 학생 제외
lost_set = set(lost) - set(reserve)
reserve_set = set(reserve) - set(lost)
for r in sorted(reserve_set):
# 앞 번호 학생부터 빌려줌
if r - 1 in lost_set:
lost_set.remove(r - 1)
elif r + 1 in lost_set:
lost_set.remove(r + 1)
return n - len(lost_set)
# 테스트
print(solution(5, [2, 4], [1, 3, 5])) # 5문제 2: 조이스틱 (프로그래머스)
def solution(name):
"""
조이스틱 최소 이동 횟수
"""
answer = 0
min_move = len(name) - 1 # 오른쪽으로만 이동
for i, char in enumerate(name):
# 상하 이동 (A → char)
answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
# 좌우 이동 최적화
next_idx = i + 1
while next_idx < len(name) and name[next_idx] == 'A':
next_idx += 1
# 오른쪽 → 왼쪽 vs 왼쪽 → 오른쪽
min_move = min(
min_move,
i + i + len(name) - next_idx, # 오→왼
i + len(name) - next_idx + len(name) - next_idx # 왼→오
)
return answer + min_move
# 테스트
print(solution("JEROEN")) # 56실전 팁
그리디 문제 판별법
# ✅ 그리디 신호
# 1. "최대/최소" + 정렬 힌트
# 2. 시간 제한 빡빡 (O(n log n) 필요)
# 3. 반례 찾기 어려움
# ❌ 그리디 불가능
# 1. 반례 존재
# 2. "모든 경우" 고려 필요
# 3. 이전 선택이 영향 (→ DP)정리
핵심 요약
- 그리디: 매 순간 최선, O(n log n)
- 증명 필수: 반례 없는지 확인
- 정렬: 대부분 정렬 후 그리디
- DP와 비교: 그리디가 더 빠르지만 항상 최적해는 아님
추천 문제
백준:
프로그래머스:
관련 글
- 투 포인터 | O(n²) → O(n) 최적화 기법 완벽 정리
- 알고리즘 시리즈 전체 목차
- 배열과 리스트
- 스택과 큐