알고리즘 기초 - 그리디 알고리즘

---

그리디 알고리즘이란?

---

그리디 알고리즘은 매 순간 가장 최선이라고 생각되는 선택을 해 나가며 최종 해답을 구하는 알고리즘이다

개념 정의

문제를 풀 때 전체적인 최적해를 한 번에 고려하지 않고, 지금 당장 가장 좋아 보이는 선택(국소적 최적해)을 반복해서 최종 해답을 만드는 방식이죠.

---

특징

---

 

• 직관적: 구현하기 쉽고, 아이디어만 떠올리면 코드로 옮기기가 간단해요.
• 빠름: 매 순간 최적 선택만 하기 때문에 복잡한 탐색이 필요 없어요.
• 정답 보장 안됨 : 모든 문제에서 항상 정답을 주지는 않아요. 특정 조건이 만족될 때만 정답이 됩니다.

즉, "빠르고 간단하지만, 믿음직하지 않을 수 있다"는 게 핵심 특징이에요.

 

---

그리디 알고리즘의 조건

---

그리디 알고리즘이 문제를 정확히 풀 수 있으려면 두 가지 조건이 충족되어야 합니다.

1. 탐욕적 선택 속성 (Greedy Choice Property)
   • 한 번의 선택이 전체 최적해의 일부여야 합니다.
   • 즉, 지금 당장 최선의 선택을 했을 때, 그 선택이 미래에 영향을 주지 않아야 해요.
   • 예: 회의실 배정 문제에서 "가장 빨리 끝나는 회의부터 고르는 방식"은 항상 최적의 해답을 보장.
2. 최적 부분 구조 (Optimal Substructure)
   • 부분 문제의 최적해가 전체 문제의 최적해로 확장될 수 있어야 합니다.
   • 예: 최소 신장 트리(MST) 문제에서 작은 트리에서의 최적 선택이 전체 트리에서도 최적 선택이 됩니다.

 

👉 이 두 조건이 없으면, 그리디 알고리즘은 정답을 보장하지 못합니다.

 

---

장점과 단점

---

• 장점
  • 단순하고 직관적
  • 속도가 빠르고 구현이 간단
  • 특정 문제(활동 선택, MST 등)에서는 무조건 최적
• 단점
  • 항상 정답을 보장하지 않음
  • 문제마다 그리디 알고리즘이 성립 가능한지 검증 필요

 

 

---

구현 예시 

---

문제: 거스름돈을 가장 적은 동전 개수로 거슬러 주기

• 동전 단위: 500원, 100원, 50원, 10원
• 목표: 입력 금액을 동전 개수 최소로 거슬러주기

 

def greedy_change(amount):
    coins = [500, 100, 50, 10]  # 큰 동전부터 사용
    result = {}
    for coin in coins:
        result[coin] = amount // coin  # 해당 동전 개수
        amount %= coin                 # 남은 금액
    return result

# 예시 실행
money = 1260
change = greedy_change(money)

print(f"{money}원을 거슬러 줄 때:")
for coin, cnt in change.items():
    if cnt > 0:
        print(f"{coin}원 동전 {cnt}개")

 

✅실행 결과

1260원을 거슬러 줄 때:
500원 동전 2개
100원 동전 2개
50원 동전 1개
10원 동전 1개

---

 

마무리

---

그리디 알고리즘은 단순히 코드를 빠르게 작성하는 방법이 아니라, 문제를 바라보는 시각을 단순화하는 사고 훈련이다. 문제를 풀기 전에 '탐욕적 선택 속성'과 '최적 부분 구조'를 떠올려보자. 그렇다면 그리디 알고리즘을 올바르게 활용할 수 있을 것이다