탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘

"현재 단계에서 가장 최적의 선택을 반복하여 최종 최적해를 구하는 알고리즘"

• 각 단계에서 최선의 선택을 하는 것이 전체적으로도 최선이라는 보장이 필요함
• DP와 달리, 이전 선택을 고려하지 않고 즉각적인 최적 선택을 수행
• 대표적인 예제: 거스름돈 문제, 최소 신장 트리(Prim, Kruskal), 최단 경로(Dijkstra)

---

탐욕 알고리즘 동작 원리

1. 현재 단계에서 가장 좋은 선택(탐욕적 선택, Greedy Choice)을 함
2. 선택한 결과를 확정하고, 다음 단계에서도 동일한 방식으로 진행
3. 최종 해답이 전체적으로 최적해인지 확인

# Pseudo Code_거스름돈 문제
FUNCTION GreedyChange(money, coins):
    coins.sort(reverse=True)  # 동전 내림차순 정렬
    count = 0

    FOR coin IN coins:
        count += money // coin  # 현재 동전 개수 추가
        money %= coin  # 남은 금액 업데이트

    RETURN count


# Full Code_거스름돈 문제
def greedy_change(money, coins):
    coins.sort(reverse=True)  # 동전 내림차순 정렬
    count = 0

    for coin in coins:
        count += money // coin  # 현재 동전 개수 추가
        money %= coin  # 남은 금액 업데이트

    return count

coins = [500, 100, 50, 10]
money = 472
print(greedy_change(money, coins))  # 8

---

탐욕 알고리즘의 시간복잡도

문제 유형	시간복잡도
거스름돈 문제	O(n)
최소 신장 트리 (Prim, Kruskal)	O(E log V)
다익스트라 알고리즘	O((V + E) log V)
활동 선택 문제 (회의실 배정 문제)	O(n log n)

---

탐욕 알고리즘 vs 동적 계획법(DP)

알고리즘	특징	시간복잡도	적용 조건
탐욕 알고리즘	현재 최적 선택을 반복	O(n log n) 이하	탐욕적 선택 속성, 최적 부분 구조 만족 시
DP (동적 계획법)	모든 경우 고려 후 최적해 선택	O(n), O(n²), O(n³) 가능	모든 경우를 비교하여 최적해 도출 필요

 

2025.01.20 - [데이터 사이언스/알고리즘] - 동적 계획법(DP, Dynamic Programming)

---

탐욕 알고리즘의 장단점

장점

 

• 구현이 단순하고 빠름 (보통 O(n log n) 이하로 동작)
• DP보다 메모리 사용량이 적음 (이전 상태를 저장할 필요 없음)
• 특정 문제에서는 최적해를 빠르게 구할 수 있음

단점

• 항상 최적해를 보장하지 않음 (탐욕적 선택이 최적해가 아닐 수도 있음!)
• 백트래킹이나 DP를 써야 하는 문제에서는 부적절할 수 있음
• 탐욕적 선택 속성이 만족되지 않으면 정답을 찾지 못함

결론

탐욕 알고리즘(Greedy Algorithm)은 매 순간 최선의 선택을 하며, 특정 문제(거스름돈, 회의실 배정, 최단 경로 등)에서는 최적해를 보장하지만, 항상 최적해를 구할 수 있는 것은 아니므로 적용 가능성을 먼저 검토해야 한다.