탐욕 알고리즘이란?

<aside> 💡 순간마다 최적을 선택해서, 문제 해답에 도달하는 방법

</aside>

• 최적해를 구하는데 사용되는 근시안적인 방법
  • 선택의 순간마다 최적을 고름
• 최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은(최대 또는 최소) 해를 찾는 문제
  • 일반적으로, 떠오르는 생각을 검증없이 구현하면 Greedy 접근이 됨
  • 최종 결과가 최적이라는 보장은 없음
• 한 번 선택된 것은 번복하지 않음
  • 비교적 단순한 알고리즘이 됨
  • 제한적인 문제들에 사용

탐욕 알고리즘 문제 해결하는 방법

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

탐욕 알고리즘 필수 요소

• 탐욕적 선택 속성 (greedy choice property)
  • 탐욕적 선택은 최적해로 갈 수 있음을 보여라 (탐욕적 선택은 항상 안전하다)
  • 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조 (optimal substurcture property)

  • 최적화 문제를 정형화하라

    → 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.

  • 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

<aside> 💡 [원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해] 임을 증명하라

</aside>

그리디 알고리즘 예시

• 분할 가능 배낭 문제 (Fractional Knapsack)
  • 배낭 짐싸기
• 활동 선택 문제 (Activity-selection)
  • 회의실 배정

예시 1) 동전 거슬러 주기

동전의 개수를 최소한으로 사용해서 거슬러 주고 싶다.