정의

그리디 거스름돈 알고리즘은 가장 큰 동전부터 최대한 사용하여 거스름돈을 만듭니다. 동전이 배수 관계(예: 500, 100, 50, 10)일 때 최적해를 보장합니다.

핵심 특성

• ✓핵심: 가장 큰 동전부터 최대한 사용
• ✓계산: 나눗셈의 몫과 나머지 활용
• ✓조건: 동전이 배수 관계일 때만 최적해
• ✓반례: [1,3,4]로 6원 → 그리디(4+1+1=3개) vs 최적(3+3=2개)

시간 복잡도