Greedy 그리디

알아보기

Greedy는 탐욕스러운 이라는 뜻이다.
선택의 순간마다 당장 제일 좋아보이는 경우를 선택한다.

여러 경우 중에 하나를 선택해야할 때, 그 순간 최적이라고 생각하는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
그 순간 선택한 결정은 지역적으로는 최적이지만, 전역적인(최종적인) 해답이 최적이라는 보장은 없다.
따라서 그리디 알고리즘을 적용하려면, 지역적으로 최적이면서 전역적으로 최적이어야 한다.

강철의 연금술사에 나오는 그리디;;; 아주 탐욕스러워 보임

조건

Greedy choice property
- 탐욕적 선택 속성
- 앞의 선택이 이후의 선택에 영향을 주지 않는다.
optimal substructure
- 최적 부분 구조
- 문제에 대한 최종 해결법은 부분 문제에 대한 최적해이다.

이러한 조건이 성립하지 않을때에도, 근사 알고리즘으로 사용할 수 있다.
근사알고리즘이란
appoximation algorithm
최적화 문제에 대한 해의 근사값을 구하는 알고리즘.
그리디는 최적해를 보장하지는 않지만 계산 속도가 빨라 실용적으로 사용할 수 있다.

 

사용 예시

일상생활에서 그리디 알고리즘을 적용할 수 있는 상황을 알아보자.

거스름돈을 돌려줄때

가게에서 3220원이 나와서 5000원을 내밀었다.
이때 직원은 1780원을 줘야하는데, 어떤 절차로 이러한 결과가 나온것일까?
1. 1000원
2. 780원이남았다.
3. 500원 
4. 280이 남았다.
5. 200원
6. 80원이 남았다.
7. 50원
8. 30원이 남았다.
9. 10원 3개
10. 끝.
위 절차에서 볼 수 있듯이, 거슬러줄 수 있는 금액 중 가장 큰 단위의 돈을 선택한다.
그리디 알고리즘을 사용해도 언제나 최적해가 나온다.