완전검색 그리디 - 탐욕 알고리즘

1. 문제 제시 : 거스름돈 줄이기

• 손님이 지불한 금액에서 물건값을 제한 차액(거스름돈)을 지불하는 문제를 생각해 봅시다.
• "어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까요?"

---

2. 탐욕(Greedy) 알고리즘

• 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법
• 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 됩니다.
• 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달합니다.
• 각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해달을 만들었다고 해서, 그것이 최적이라는 보장은 없습니다.
• 일단, 한 번 선택된 것은 번복하지 않습니다. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며, 또한 제한적인 문제들에 적용됩니다.
• 최적화 문제(optimization)란 가능한 해 들 중에서 가장 좋은(최대 또는 최소) 해를 찾는 문제입니다.

---

3. 탐욕 알고리즘의 동작 과정

---

4. 배낭 짐 싸기(Knapsack)