Greedy Algorithm

Greedy algorithm

• 선택의 순간마다 현재 최적의 답을 선택해 최종 해답에 도달하는 방법
• 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다.

조건

• 이전 단계의 선택이 이후 단계의 선택에 영향을 주지 않아야 한다
• 문제의 대한 최적해가 부분 문제에 대해서도 최적해여야 한다.

문제예시

• 거스름돈을 동전의 개수 최소한으로 하여 거슬러 주는 문제
• 강의실에서 여러 수업을 하려할 때 가장 많은 수업을 할 수 있는 경우를 고르는 것. - 조욜시간이 가장 빠른 것 부터 선택.