탐욕 알고리즘
동적 계획법과 마찬가지로 최적화 문제의 답을 얻기 위해 사용한다.
탐욕이라는 이름은 각 단계의 부분 문제를 풀 때 근시안적으로 최적해를 구한다고 해서 붙여진 이름
즉 욕심을 낸다는 의미보다는 가까운 것만 바라보게 하는 효과에 초점을 맞춘 것.
탐욕 알고리즘으로 풀 수 있는 문제는 동적계획법 처럼 대상 문제가 최적 부분 구조를 갖고 있어야 함
알고리즘
1.
해 선택 : 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합 (Solution Set)에 추가한다.
2.
실행 가능성 검사 : 새로운 부분해 집합이 실행가능한지를 확인한다. 문제의 제약 조건을 위반하지 않는지 검사.
3.
해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 1의 해 선택부터 다시 시작한다.
편의점 점원의 거스름돈 줄이기
“어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?”
1.
해 선택 : 가장 좋은 해를 선택해본다. 단위가 큰 동전으로만 거스름돈을 만들면 동전의 개수가 줄어든다. 따라서 현재 고를 수 있는 가장 단위가 큰 동전을 하나 골라 거스름돈에 추가한다.
2.
실행 가능성 검사 : 거스름돈이 손님에게 내드려야 할 액수를 초과하는지 확인한다. 초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고, 1로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가한다.
3.
해 검사 : 거스름돈 문제의 해는 당연히 거스름돈이 손님에게 내드려야 하는 액수와 일치하는 것이다. 거스름돈을 확인해서 액수에 모자라면 다시 1로 돌아가 거스름돈에 추가할 동전을 고른다.
