탐욕법 - Greedy

탐욕법 (Greedy algorithm)

매 순간마다 최선의 경우만을 선택하고, 다른 경우나 나중을 고려하지 않는다.

• 선택하는 그 순간의 경우에는 최적이지만, 그 선택들이 모여 최종적인 답이 나왔을때 최적이라는 보장이 없다는 문제점이 있다.
• 모든 경우를 다 보지 않으니 완전 탐색보다 빠르고, 어떤 경우가 최선인지 규칙성을 찾는게 탐욕 알고리즘 문제의 포인트가 된다.
  => but, 해당 문제가 그리디 문제인지 판별하는것 자체가 매우 어렵다.

탐욕법이 성립하는 두가지 조건

1. 탐욕적 선택 속성
   • 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조
   • 문제의 최종 해결 방법이 결국 매 순간 마다의 해결 방법이랑 같아야 한다.

탐욕법 예시

탐욕법을 사용할 수 있는 경우

• 10원, 50원, 100원, 500원 동전들을 무한하게 갖고 있다.
• 손님에게 900원을 거슬러 주려고 할 때, 동전을 최소한으로 주는 방법은?
• 동전 단위를 살펴보면 작은 동전이 큰동전의 배수 관계를 가지고 있기 때문에 큰 동전을 먼저 거슬러 줘도 된다. => 탐욕법 사용 가능

탐욕법을 사용할 수 없는 경우

• 100원, 400원, 500원 동전들을 무한하게 갖고 있다.
• 손님에게 800원을 거슬러 주려고 할 때, 동전을 최소한으로 주는 방법은?
• 동전 단위를 살펴보면 배수 관계가 아닌것이 있기 때문에 큰 금액을 먼저 거슬러 주는게 최종의 답에서도 최선이라는 보장이 없다.

예제 및 알고리즘

백준 - 11047 동전0 https://www.acmicpc.net/problem/11047

• 최소한의 동전만 사용하여 합을 K로 만든다.
• N개의 동전 가치와 K라는 가치의 합이 첫번째 입력값으로 주어진다.
• 동전 가치인 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
  => Ai는 Ai-1의 배수라는 조건 때문에 탐욕법을 사용할 수 있다.
  

Greedy 방법

# N = 10, K = 4200
N, K = map(int, input().split())

# 큰 단위의 동전부터 사용하기 위하여 reverse()를 이용한다.
coins = [int(input()) for _ in range(N)]
coins.reverse()

count = 0
for coin in coins:
    # 동전단위 보다 구해야 하는 값이 높을때 현재 사용할 수 있는 최대 금액의 동전 인것이다.
    if K >= coin:
        # 현재 동전으로 구하는 금액을 나눠서 몫을 카운팅한다
        count += K // coin # => 4 (1000원)
        # 구하는 금액에서 몫만큼의 값을 빼고 나머지를 구한다.
        # 나머지가 다음 단계에서 구해야 하는 값이 되는것이다.
        K %= coin # => 4200 % 1000 = 200 , 4

print(count) # => 6