탐욕법 (greedy) 이란?

Greedy란?

카테고리가 탐욕법이라고 되어있는데, 이 탐욕법에 대해서 먼저 알아보자.

 

탐욕법이란 DP(Dynamic Programming)과 상호보완하며 사용되는데, 이번에는 탐욕법에 대해서만 알아보자.

탐욕법이란 기본적으로 현재의 최선을 반복해서 선택하는 해결방법이다.

 

아래의 이미지를 한번 살펴보자

위의 트리에서 실제 가장큰수는 99이다. ,하지만 탐욕법으로 하면 가장큰수는 12 이다.

 

왜냐하면 탐욕법은 첫번째 분기에서 1과 9중에 큰 9를 고르고, 그다음에는 3과 12중에 12를 고르기 때문이다.

 

이렇듯이 탐욕법은 최선의 해결법이 되지는 않지만, 빠른 결과를 산출해 낼수있는 장점이 있다.

탐욕법의 적절한 예

탐욕법의 적절한 사용순간은 언제일까?

 

탐욕스러운 선택 조건(Greedy choice property) - 해답이 다음 해답에게 영향을 주지 않는 독립적 연산
최적 부분 구조 조건(Optimal Substructure) - 문제의 최종해결 방법이 각각의 부분 문제의 최적해결방법 일때

 

즉, 각각의 하위 해답이 다음 문제풀이에 영향을 주지 않으면서도 하위의 최선의 해답의 집합이 전체의 최선해답일때 사용가능하다.

 

예시를 들자면 여러분이 77,000원을 지폐로 받으려한다 가정해보자.

 

가장 큰 5만원으로 1장 -> 5만원 + 27,000원

만원으로 2장 -> 5만원 + 1만원 *2 + 7,000원

5천원으로 1장 -> 5만원 + 1만원 *2 + 5천원 + 2,000원

천원으로 2장 -> 5만원 + 1만원 *2 + 5천원 + 천원 *2

 

위의 예시와 같이 순간의 최선으로 해결해도 다음풀이(5만원 이후 만원)에 영향을 주지 않으며,

 

이렇게 나온 해답이 전체의 최선의 해답이기 때문에 가능하다.