Greedy Algorithm

Greedy Algorithm

매번 선택의 순간마다 최적의 상황을 쫓아 최종적인 해답에 도달하는 방법

 

탐욕 알고리즘의 해결 방법

1. 선택 절차 : 현재 상태에서 최적의 해답 선택
2. 적절성 검사 : 선택된 해가 문제의 조건에 만족하는지 검사
3. 해답 검사 : 문제가 해결되었는지 확인 후 해결되지 않았다면 선택 절차로 돌아가 다시 반복

* 실생활 사례

손님으로 온 박씨가 "과자" , "음료" 를 선택해 물건 가격은 4040원이 나왔습니다.
손님은 계산을 위해 5000원을 내밀었고, "동전의 개수를 최소한"으로 거슬러 달라고 요청하였습니다.
4040원의 동전의 개수를 최소한으로 주는 방법이 탐욕 알고리즘의 대표적인 예제입니다.

1. 선택 절차
거스름돈 동전 개수를 줄이기 위해 현재 가장 가치있는 동전을을 우선 선택
 : 500원 -> 100원 -> 50원 -> 10원

2. 적절성 검사
1번 과정을 통해 동전들의 합이 거슬러 줄 금액을 초과하는지 검사합니다.
초과하면 가장 마지막에 선택한 동전 삭제 후, 1번으로 돌아가 한 단계 작은 동전을 선택

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

거스름돈 960원에 대한 위의 과정을 거치는 과정을 보겠습니다.

[1]
1. 500원 2개
2. 값이 초과됨으로 500원 1개, 100원 1개 선택

[2]
1. 500원 1개, 100원 5개
2. 값이 초과됨에 따라 500원 1개, 100원 4개, 50원 2개 선택 ....

이러한 과정을 거치게 됩니다.
그러면 총 500원 1개, 100원 4개, 50원 1개, 10원1개를 선택하게 됩니다.

 

탐욕 알고리즘의 반례 ( 마시멜로 실험 )

- 조건 : 지금 마시멜로를 받겠다고 하면 1개를 받고, 1분 기다렸다가 받으면 2개를 받을 수 있음

- 반례사항

: 탐욕 알고리즘에 따라 "현재" 최적의 선택을 하므로 1개의 마시멜로를 선택합니다.

 하지만 전체적으로 보면 1분뒤에 2개를 받는게 최적의 선택이 되므로 그리디 알고리즘은 최적의 해를 이끌어내지 못합니다.

 

탐욕 알고리즘이 최적의 해를 구하는 조건

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

 

결론

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만,

어느정도 근사한 값을 빠르게 도출해준다는 장점이 있습니다.