[Algorithm] 순간의 최적 선택 greedy 탐욕법

탐욕적 알고리즘(욕심쟁이 알고리즘)이라고도 하며, 

 

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식

 

 

내가 돈을 많이 받기 위해 문을 통과해야하면 어떤 문을 선택할 것인가 ?

--> 10만원

이번 문을 통과해서 많은 돈을 받으려면?

--> 8만원

 

총 18만원을 받았다 

현재로썬 최적의 선택일지 모르지만

이렇게 보면? 사실 그렇게 좋은 선택은 아니다

greedy 알고리즘은 모든 사항을 고려하지 않고, 상황에 맞는 항상 최적의 선택을 할 수밖에 없다.

그렇다고 최악의 선택도 아니기 때문에 근사치를 추정하기 위해 많이 사용한다. 

 

 

탐욕 알고리즘이 잘 작동하는 문제는 두 가지 조건이 만족해야한다.

1. 탐욕스런 선택 조건 :
앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이다

 예를 들어 위에서 2번째 문들의 값들이 1과 100으로

                           고정 되어있는 것이 약속이 된다면?

 

 

 

 

2. 최적 부분 구조 조건  : 

문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다

 예를 들어 문이 가장 큰 돈부터 정렬되어  나온다면?