탐욕알고리즘 - Greedy Algorithm, 동적 계획법 - Dynamic Programming

* 탐욕 알고리즘

미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 알고리즘.

각 단계에서 최선의 선택을 한 것이므로, 전체적으로도 최선을 바라는 알고리즘이다.

-> 여러 경우 중 하나를 선택할 때 그 상황에서 가장 좋다고 생각하는 것을 선택하는 것.

     하지만 이 선택이 최선의 선택이지 최고의 선택은 아니다.

 

즉, 최적해를 구하는 상황에서 사용하는 알고리즘.

 

시작할 때는 큰 숫자를 택했지만 결과는 더 작은 숫자가 리턴됨. 

 

최선의 선택을 했지만 최적의 해답을 찾지는 못했다.

 

Greedy의 가장 큰 장점은 속도에 있다.

Greedy 방법이 통하는 몇몇의 문제에서는 최적해를 빠르게 산출해 낼 수 있다.

 

빠른 계산 속도의 장점으로 Dynamic Programming의 단점을 보완하는 개념으로 사용할 수 있다.

 

해 - 방정식, 혹은 부등식을 충족하는 미지수의 값.

최적해 - 선형 계획법에서 제약 조건을 충족시킬 수 있는 해 가운데 목적 함수 값을 최대 또는 최소로 만드는 값.

 

 

그리디 알고리즘 예제

362 원의 물건을 구매하는 상황에서 가진 동전 1원, 50원, 100원의 동전의 수를 가장 적게 지불하기.

동전의 종류 coin, 지불 해야 하는 금액 value, 동전이 종류별로 어떻게 사용되는지 dic.

 

 

* 동적 계획법

전체 문제를 여러개의 하위 문제로 나누어 풀고, 하위 문제들의 해결방법을 결합하여 최종 문제를 해결하는 문제 해결 방식.