탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘이란?

• 탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법니다.
• 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법니다.
• 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다
• 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

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

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

탐욕 알고리즘을 적용하기 위한 조건

• 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적  부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

탐욕 알고리즘 예지 - 매트로이드

하나몬은 오늘도 편의점에서 열심히 아르바이트하고 있다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로하여 거슬러 달라고 하였다.

이때 하나몬은 어떻게 거슬러 주어야 할까?

탐욕 알고리즘의 문제 해결 과정을 적용

1. 선택 절차
   1. 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
2. 적절성 검사
   1. 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다.
   2. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
3. 해답 검사
   1. 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.
   2. 액수가 부족하면 1번 과정부터 다시 반복한다.