탐욕 알고리즘(Greedy Algorithm)

• Greedy "탐욕스러운, 욕심 많은"

• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

✨ 탐욕 알고리즘 문제 해결 단계

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

✨ 탐욕 알고리즘 적용 조건

1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

• 이러한 조건을 만족하지 않으면 탐욕 알고리즘은 최적의 해를 보장하지 못한다.
• 최적의 결과를 도출하는 건 아니지만, 최적에 근사한 값을 빠르게 도출할 수 있어서 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.
  • 근사 알고리즘(Approximation Algorithm)
    • 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘
    • 가장 최적화 되는 답을 구할 순 없으나 비교적 빠른 시간내에 어느정도 보장된 근사해를 계산할 수 있다.

---

✨ 탐욕 알고리즘 적용 예시

5000원 - 4,040 = 960원 거슬러줄 때
1. 선택 절차 : 거스름돈 동전 개수를 줄이기 위해 가장 가치가 높은 동전을 우선 선택
2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사. 초과하면 가장 마지막에 선택한 동전을 삭제하고 1번으로 돌아가 한 단계 작은 동전 선택
3. 해답 검사 : 선택된 동전들의 합이 거슬러줄 금액과 일치하는지 검사. 부족하다면 1번부터 반복
--> 이 과정을 통해 얻은 문제 해답
---> 가장 가치가 높은 동전인 500원 한개를 먼저 거슬러주고 잔액을 확인한뒤 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러줌

---

💡 정리

탐욕 알고리즘 : 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식

하지만 항상 최적의 결과를 보장하는건 아님

마시멜로 실험
지금 마시멜로를 받겠다고 말하면 1개를 받을 수 있지만, 1분을 기다렸다가 받는다면 2개를 받을 수 있다.
greedy는 "현재"에 최선인 선택을 하기 때문에 마시멜로를 당장 받아내어 1개를 받게 되지만,
전체적으로 보게 되면 1분 뒤에 받는 2개가 최적의 선택이 된다.

조건을 만족하는 특정한 상황이 아니라면 탐욕 알고리즘은 최적의 해를 보장하지 못함