탐욕 알고리즘 Greedy Algorithm
- 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법
- 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다
- 각 선택의 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없다
- 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다
탐욕 알고리즘의 동작 과정
- 해 선택: 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합 (Solution Set)에 추가한다
- 실행 가능성 검사: 새로운 부분해 집합이 실행 가능한지 확인한다 곧, 문제의 제약 조건을 위반하지 않는지를 검사한다
- 해 검사: 새로운 부분해 집합이 문제의 해가 되는지를 확인한다 아직 전체 문제의 해가 완성되지 않았다면 1. 의 해 선택부터 다시 시작한다
탐욕 알고리즘 예
********거스름돈 줄이기********
→ “어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?”
해 선택
여기에서는 멀리 내다볼 것 없이 가장 좋은 해를 선택한다 단위가 큰 동전으로만 거스름돈을 만들면 동전의 개수가 줄어들므로 현재 고를 수 있는 가장 단위가 큰 동전을 하나 골라 거스름돈에 추가한다
실행 가능성 검사
거스름돈이 손님에게 내드려야 할 액수를 초과하는지 확인한다 초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고, 1. 로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가한다
해 검사
거스름돈 문제의 해는 당연히 거스름돈이 손님에게 내드려야 하는 액수와 일치하는 셈이다. 더 드려도, 덜 드려도 안 되기 때문에 거스름돈을 확인해서 액수에 모자라면 다시 1. 로 돌아가서 거스름도에 추가할 동전을 고른다.