탐욕 알고리즘이란?

• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

탐욕 알고리증 속성

• 탐욕적 선택 속성(Greedy Choice Property) : 각 단계에서 탐욕스런 선택이 최종답을 구하기 위한 최적의 선택.
• 최적 부분 구조(Optimal Substructure) : 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것
• 중복되는 부분문제(Overlapping Subproblem)

해결방법

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

탐욕알고리즘 예시

A라는 손님은 5000원을 지불하고 4080원의 물건값을 계산했다. 거스름돈은 최소한의 동전갯수로 하려고 한다.

sol)
1. 선택 절차 - 동전 중에서 가장 값비싼 동전을 시작해서 점점 present value가 낮은 동전을 선택한다.
2. 적절성 검사 - 선택한 동전들의 합이 거슬러 줄 금액을 초과하는지 검사. 초과하면 가장 마지막 선택한 동전을 삭제하고 그 다음 낮은 value의 동전을 선택한다.
3. 해답검사 - 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.

note!! - 이 문제는 매트로이드. 즉, Greedy 알고리즘을 이용하여 최적해를 구할 수 있는 문제구조.

Greedy 알고리즘 문제풀이

1. 백준, ATM
   a = [3,1,4,3,2]
   b = sorted(a)

   part = 0
   answer = 0
   for i in range(len(b)):
   part = part + b[i]
   answer = answer + part
   print(sum) #32

2. 백준, 전자레인지

   a = 300
   b = 60
   c = 10

   def micro(T):
   if T % 10 !=0:
   print(-1)
   else:
   aT = T // a
   bT = (T % a) // b
   cT = (T % b) // c
   print(aT, bT, cT)

   micro(360) #1, 1, 0

출처: https://hanamon.kr/