(이전까지는 욕망의 항아리만 알고있었음 ㅋ 😝)

---

Greedy Algorithm

Greedy의 사전적 정의는 "탐욕스러운, 욕심 많은" 이라는 의미를 가진다.

탐욕 알고리즘은 결정의 순간마다 당장 눈앞에 보이는 최적의 상황만을 탐욕적으로 쫓아 최종적인 해답에 도달하는 방법이라고 한다.

탐욕 알고리즘의 문제 해결법

1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택합니다.
2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사합니다.
3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복합니다.

---

간단한 예시로는 거스름돈을 돌려주는 상황을 볼 수 있다.

손님으로온 B는 4,040원이라는 결제 금액이 나왔다. 그는 계산을 위해서 5,000원을 주었다. 이때 거스름돈은 동전의 갯수를 최소한으로 하여 달라고 하였다. 동전을 어떻게 주어야 할까?

1. 선택 절차

   • 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택!

2. 적절성 검사

   • 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사!
   • 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택!

3. 해답 검사

   • 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사!
   • 액수가 부족하면 1번 과정부터 다시 반복!

   -> 500원 1개, 100원 4개, 50원 1개, 10원 1개 로 거슬러 주기

---

마무리

탐욕 알고리즘은 문제를 해결하는 과정에서 그 순간순간마다 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식입니다. 하지만 도둑의 예와 같이 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 합니다.

예시는 간단하지만 실제 알고리즘 문제에 접했을때에는 어떻게 접근해야하는 아직까지는 어색하고 어렵다...
개념만 이해한다고 되는것은 아닌것같고 문제를 자주 접하고 생각하는 연습을 계속 해야겠다.