<aside> 💡

그리디 알고리즘

• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 것이다. </aside>

문제 상황

동전 종류: 500, 400, 100

금액: 800

• 그리디(탐욕) 방법: 가장 큰 동전부터 최대한 많이 쓴다.
  • 500 한 장 → 남은 300 → 100 세 장
  • 총 4장(= 500×1 + 100×3)
• 최적: 400 두 장
  • 총 2장(= 400×2)

예시는 그리디가 실패한 반례다. “큰 동전부터”가 항상 최소 장수를 보장하진 않는다.

왜 그리디가 실패했나?

그리디는 매 순간 지역적으로 “제일 좋아 보이는 선택”을 하지만,

다음 선택의 여지를 망칠 수 있다.

여기서는 처음에 500을 쓰는 순간 남는 300을 400으로 처리할 수 없게 되어 100을 3장 써야 했다.

반대로 처음부터 400을 쓰면 400이 한 번 더 정확히 들어맞아 2장으로 끝난다.

• 맞는 경우(충분조건 예)

  • 동전 값이 작은 값의 배수 체계일 때(예: 1, 10, 100, 1000 처럼 각 동전이 바로 아래 동전의 배수)

    이런 계에서는 큰 것부터 쓰는 게 항상 최적(증명 가능)

  • 실제 화폐(미국 1·5·10·25, 한국 10·50·100·500 등)는 설계상 대부분 그리디가 맞도록(정준 체계) 되어 있음