[Algorithm] Dynamic Programming vs. Greedy Algorithm

 

동적계획법(Dynamic Programming)은 지난 포스팅에서 살펴봤습니다.

2025.02.19 - [프로그래밍/Python 관련 정보] - [Algorithm] Dynamic Programming vs. Recursion

[Algorithm] Dynamic Programming vs. Recursion

이번에는 동적계획법과 탐욕(Greedy) 알고리즘을 비교해보겠습니다. 

 

탐욕(Greedy) Algorithm : 순간순간 마다의 최선의 결정하는 방식으로 최종 해답에 도달하는 문제 해결 방식을 말합니다. 이 방법이 통하는 경우 빠른 계산 속도를 확보할 수 있지만 모든 문제를 해결할 수는 없습니다. 

 

Greedy Algorithm을 적용하기 위한 2가지 조건

1) 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2) 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결 방법이다.

 

Dynamic Programming을 적용하기 위한 2가지 조건

1) 큰 문제를 작은 문제로 나눌 수 있다(어떻게 구할지 막막한데 구하는 대상 인접항들을 알면 그 관계를 이용해서 문제를 해결할 수 있는 경우-점화식).
2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 정답이다. 

 

 

유사한 세팅의 문제 2개를 각각 풀어보면서 비교해봅시다. 

---

손님에게 거슬러 줘야할 돈이 N원 일때, 거슬러줘야 할 동전의 최소 개수를 구하여라 (거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다고 가정)

출처: 이것이 취업을 위한 코딩테스트다 "거스름돈"

n = 1260
count = 0

coin_types = [500,100,50,10]

for coin in coin_types:
	count += n // coin
	n %= coin

print(count)

 

---

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이 때 각 종류의 화폐는 몇 개라도 사용할 수 있으며 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하시오.

출처: 이것이 취업을 위한 코딩테스트다 "효율적인 화폐구성"

n, m = map(int, input().split())

array = []
for i in range(n):
    array.append(int(input()))

d = [10001] * (m + 1)

d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

2, 3 => 15의 예시를 가지고 생각해 볼까요? 주어진 화폐단위가 2와 3이기 때문에 구하고자 하는 n번째 수열의 값은 그 화폐단위만큼 뒤로 퇴각한 값의 영향을 받을 것이라 생각할 수 있습니다. 예를 들어 \(a_{7}\)은 3원짜리 1개, 2원짜리 2개로 만들 수 있어 3인데 \(a_{4}\)에서 3원짜리를 하나 더 추가해서 만들 수 있고, \(a_{5}\)에서 2원짜리 하나를 더 추가해서 만들 수 있습니다. 두 방법 중 어떤것이 최적인지는 알 수 없으니 비교해서 작은걸 택해야 하겠지만 이제 점화식을 만들 수 있고 dynamic programming 문제 해결의 실마리도 찾았다고 볼 수 있습니다. 

 

from math import inf
n, m = [int(x) for x in input().split()]

coins = [int(input()) for _ in range(n)]

ans_ls = m*[-inf]

for i in coins:
    ans_ls[i-1] = 1

for s in range(min(coins), m):
    try:
        ans_ls[s] = min([ans_ls[s-x] for x in coins if ans_ls[s-x]!=-inf])+1
        # if ans_ls[s-x]!=-inf 조건을 넣주지 않으면 -inf가 들어간 경우 항상 최소값이 -inf가 되는 문제
        # [-inf, 2] 인 경우에는 2를 가져와야하지만 -inf가 되어버림
    except:
        # 만약 모든 ans_ls[s-x] 케이스에 대해서 -inf이었다면 min( [] ) 이 되어 에러 발생 (cf. SQL min)
        continue

print(ans_ls[m-1] if ans_ls[m-1]!=-inf else -1)