그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란?

- 다이나믹 프로그래밍이 모든 경우를 확인 한다는 점에서 고안된 알고리즘

- 매 선택마다 가장 최적인 답을 선택하여 결론을 도출 --> 알파고: 자신 차례마다 가장 승률이 높은 수를 선택

- but, 매 선택마다 최적이지만 결과가 최적이라는 보장 없음

- 마시멜로 실험: 당장은 1개, 기다리면 2개 --> 최적해: 기다리고 2개 먹기

- 하지만 그리디 알고리즘은 지금 최적의 선택인 1개를 선택 --> 최적해 아님

그러면 어떤 경우에 잘 동작하는가?

- 탐욕 선택 속성(greedy choice property): 한번의 선택이 다음 선택과는 무관

- 최적 부분 구조(optimal substructure): 매 순간의 최적해 --> 문제에 대한 최적해

그리디 알고리즘 코드 구현

- 백준 - 설탕 배달: https://www.acmicpc.net/problem/2839

- 설탕 N kg을 3kg, 5kg봉지에 담아야 하는데 봉지의 수를 최소화

  1. 최적 부분 구조: 매 순간 봉지의 수를 최소화하려는 행위(3kg 봉지 보다 5kg 봉지 사용)는 문제에 대한 최적해(봉지의 수 최소화)

  2. 탐욕 선택 속성: 전에 5kg 봉지를 선택하든 3kg 봉지를 선택하든 상관없이 현재 남아있는 무게를 가지고만 판단하여 선택

- 그리디 알고리즘: 5kg 봉지로만 담는 것이 최선

- 만약 5kg 봉지로만 담는 것이 불가능하면?

- 5kg 봉지를 하나 줄이고 3kg 봉지를 사용함

- 이를 반복함 --> 만약 담는 것이 불가능하면 -1 return

  • 설탕 배달(그리디 알고리즘)

- 설탕의 무게는 N kg

  1. 5kg 봉지 선택(최적 판단)

  2. 5kg 봉지 선택(최적 판단)

  3. 5kg 봉지만 계속 선택 --> total: k 번 선택(최적 판단)

  4. 만약 남은 무게가 예컨데 4kg 이라 5kg 봉지에 담지 못한다면 3kg 선택(최적 판단)

  5. 3kg 에 담고나면 1kg 이 남음 --> 어느 봉지에도 담지 못함

  6. 5kg 봉지를 k - 1번 선택하고 3kg 봉지를 선택

  7. 5kg 봉지를 0번 선택할 때 까지 반복 --> 이 경우에도 답이 없다면 해가 존재하지 않음

N = int(input())

def sugar(n):
    k = n // 5
    l = n % 5
    
    for i in range(k+1):
        if l == 0:
            return k
            break
        elif l % 3 == 0:
            return k + l // 3
            break
        else:
            l += 5
            k -= 1
    
    return -1
    
print(sugar(N))
        

21

- 설탕 무게가 101kg 일시 5kg 19개, 3kg 2개를 선택