Greedy(탐욕 기법)

현재상황에서 당장 좋은 것만 고르는 알고리즘 설계 기법
BGM : 아리아나그란데 - Greedy

개요

• 최적해를 구하는데 주로 사용되는 근시안적인 방법이다.
• 최적화 문제란 가능한 해들 중에서 가장 좋은(최대, 최소)해를 찾는 문제이다.
• 여러 경우를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식이다.
• 한번 선택한 것은 번복하지 않아서 단순하거나 제한적인 문제들에 적용된다.
• 반드시 최적해를 구한다는 보장은 없다.

특징

• 현재의 선택이 나중에 미칠영향은 고려하지 않는다.
• 외우지 않아도 풀 수 있는 알고리즘이다.
• '창의력' 이 필요하다.

조건

• 항상 최적해로 갈 수 있음을 증명하면 항상 안전한 선택이 된다.
• 후의 경우가 상위 배수의 전제를 갖고있어야 한다.(예 : 거스름돈 문제)

어떤 상황에서 사용하는가?

• 단순히 현재상황에서 가장 좋은 것을 선택해도 풀 수 있는 문제
• 문제풀이를 위한 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야한다.
• 바로 문제 유형을 파악하기 어려운 문제

* 손님이 지불한 금액에서 거스름 돈을 지불하는 문제에서 지폐와 동전의 개수를 최소한으로 줄이는 경우
* 배낭 짐싸기문제 
    + Knapsack 문제 유형 - 물건을 쪼갤수 없는 경우 
    + Fractional Knapsack 유형 - 부분적으로 담는 것이 허용되는 문제