Greedy Algorithm : 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
ex) 거스름돈 주기
단계
- 선택 절차 : 현재 상태에서의 최적의 해답을 선택
- 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사
- 해답 검사 : 원래의 문제가 해결되었는지 검사하고 , 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복
Greedy algorithm이 적용될 수 있는 조건 2가지
- 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않을 때
- 최적 부분 구조 : 문제에 대한 최종 해결방법이 부분 문제에 대한 최적 문제 해결 방법일 때