욕심쟁이 방법론

이번 포스팅은 욕심쟁이 방법론 입니다.

 

욕심쟁이 방법론은, 작은 문제에 대한 최선의 선택을 하는 알고리즘 방법론입니다.

 

무슨소리인지 감이 잘 안옵니다.

 

아래 예시를 보겠습니다.

 

집게사장으로 알아보는 욕심쟁이 방법론

1달러당 무게가 1이라고 가정해 봅시다.

 

이때 집게사장님은 욕심쟁이 이기 때문에, 무조건 큰 돈은 우선으로 줍습니다.

 

그러면 5달러를 모두 담고, 남은 공간에 3달라를 담는것이 주어진 상황에서 최선의 선택이겠죠?

 

하지만 이렇게 하면 최적의 이익을 얻을 수는 없습니다.

 

 

 

욕심쟁이 방법론은 동적 프로그래밍 방법론과 유사하게

 

작은 소문제에 대한 해를 찾아서, 전체 문제의 해를 찾는 알고리즘 계획 방법론입니다.

 

동적프로그래밍 방법론은 이전 단계의 최적해를 기억해서 전체 문제의 최적해를 찾는다면

 

욕심쟁이 방법론은 욕심을 부려서 모든 소문제의 Condition에서 최적의 선택을 하는 방법론입니다.

(집게사장님도 5달러를 줍는것이 가장 우선이기 때무이었기 때문이죠 ^_^;;)

 

 

 

하지만 해당 방법론은 주어진 Condition에서 최적해를 구하지만, 전체 최적해를 구하는 방법이 아닙니다.

 

때문에 위에 집게사장님처럼 전체상황을 볼 때 최적해와는 차이가 발생합니다.

 

 

욕심쟁이 방법론은 주로 최적성의 원리가 적용되는

 

최적해를 산출하는 문제를 해결할 때 알고리즘계획 방법론으로 사용됩니다.