Greedy Algorithm (탐욕 알고리즘)

설명

• 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달
• 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것이 최종적인 해답으로 적합하다는 보장은 없음
• 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy적인 접근

 

동작 과정

1. 해 선택: 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가
2. 실행 가능성 검사: 새로운 부분해 집합이 실행 가능한지 확인
   • 즉, 문제의 제약 조건 등을 위반하지 않는지를 검사
3. 해 검사: 새로운 부분해 집합이 문제의 해가 되는지를 확인
   • 아직 전체 문제의 해가 완성되지 않았다면 1. 의 해 선택부터 다시 시작

 

예시

거스름돈 줄이기

어떻게 하면 손님에게 거스름돈으로 주는 동전의 개수를 최소한으로 줄일 수 있을까?

1260 원이라는 금액을 500원, 400원(가상의 단위), 100원, 50원, 10원으로 구성하여 거슬러 주려고 한다.

 

1. 해 선택: 멀리 생각할 것 없이 가장 좋은 해를 선택한다.
   • 단위가 가장 큰 동전으로 먼저 차감하며 거스름돈으로 추가한다.
   • 500원 * 2개 + 100원 * 2개 + 50원 * 1개 + 10원 * 1개 (총 6개)
2. 실행 가능성 검사: 거스름돈이 손님에게 내드려야 할 액수를 초과하는지 확인
   • 초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고, 1.로 돌아가 현재보다 한 단계 작은 단위의 동전을 추가
3. 해 검사: 거스름돈 문제의 해는 당연히 거스름돈이 손님에게 내드려야 하는 액수와 일치하는 셈
   • 더 드려도, 덜 드려도 안되기 때문에 거스름돈을 확인해서 액수에 모자라면 다시 1.로 돌아가 추가할 동전을 선택

• 탐욕 알고리즘으로 접근하였을 때, 최적해가 아닌 경우가 발생
  • 400원 * 3개 + 50원 * 1개 + 10원 * 1개 (총 5개)
  • 이런 경우 다시 해 선택 단계로 돌아가 다시 진행해야 함