다이나믹 프로그래밍 DP

컴퓨터에서 연산 속도에 한계가 있고 메모리 공간도 있어 데이터 개수에 따른 한정적이라는 문제점이 있습니다. 다만 메모리 공간을 더 사용해 연산 속도를 크게 올릴 수 있는데 알고리즘이 하나로 다이나믹 프로그래밍을 많이 사용합니다.

 

다이나믹 프로그래밍이란?

어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘입니다. 쉽게 이전의 해를 기억하면서 문제를 해결하는 방법입니다.

 

다이나믹 프로그래밍 조건

부분 반복 문제(Overlapping Subproblem)  

최적 부분 구조(Optimal Substructure)

부분 반복 문제(Overlapping Subproblem)

동일한 작은 문제들이 반복해서 이용될 때 사용가능합니다. 

쉽게 이전 해를 리스트나 배열에 저장했을 때 재사용할 수 있어야 합니다. 예를들어 파보나치 문제를 해결해야할 때 재귀함수로 구현했을 경우 이전 해를 구했어도 다음해에서 이용되지 않습니다. 하지만 리스트에 이전 값을 기록하게 된다면 이전의 구한 값을 재사용해서 동일한 작은 문제들을 반복 이용해 해결할 수 있습니다.

 

최적 부분 구조(Optimal Substructure)

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 해를 찾을 수 있는 경우를 말합니다. 따라서 특정 문제의 정답은 문제의 크기와 상관없이 항상 동일하게 됩니다.

예를 들어 최소한의 동전 거스름돈 문제의 경우 해당 동전에 대한 부분 문제의 최적 결과를 저장하고 전체 문제의 해를 찾을 수 있습니다.

 

다이나믹 프로그래밍 사용 예제

파보나치 수열

예를 들어 꼬리를 무는 함수(파보나치, 팩토리얼)를 재귀함수로 구현했을 경우 작은 숫자는 쉽게 구하지만 숫자가 커질수록 시간이 많이 소요되는 것을 알 수 있습니다. 이런경우 메모리 공간에 리스트나 배열을 선언해 이전에 계산한 값을 기록해 시간을 크게 단축할 수 있습니다.

import math
import time

start = time.time()
def fibo(x):
    if x == 1 or x== 2:
        return 1
    return fibo(x-1) + fibo(x-2)
fibo(35)
end = time.time()

print(f"{end - start:.5f} sec")

start = time.time()
d = [0] * 100

def fibo(x):
    if x==1 or x==2:
        return 1
    if d[x] != 0 :
        return d[x]
    else:
        d[x] = fibo(x-1) + fibo(x-2)
    
end = time.time()

print(f"{end - start:.5f} sec")

 

위 코드는 재귀함수를 이용해 다이나믹프로그래밍을 하지 않았을때와 적용했을 때 속도의 차이입니다. 이 처럼 메모이제이션을 이용해 한 번 푼 문제를 리스트에 저장했을 때 더욱 효율적으로 문제를 해결하는 것을 확인할 수 있습니다.

 

동전 찾기

동전 찾기 같은 경우 500,100,50,10 같이 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수일 때는 최소한의 거스름돈을 거슬러 줘서 탐욕법으로 해결할 수 있지만 500,400,100 같은 탐욕법으로 해결할 수 없습니다. 이 때 최적의 해를 구하기 위해서 다이나믹 프로그래밍을 이용할 수 있습니다.

예를 들어 800원의 동전을 최소한의 동전개수로 거슬러줘야할 경우 500, 100, 50, 10 경우 500원 하나 100원 3개로 총 4개를 거슬러 줘야하지만 동전이 500,400,100 일 경우 최적의 동전 개수는 400원 2개 총 2개를 거슬러 줘야합니다. 

 

def min_coin_greedy(coins , V):
    count = []
    for i in range(len(coins)):
        cnt = V // coins[i]
        count.append(cnt)
        V-= cnt * coins[i]
    return count


coins = [500,100,50,10]
V=800
print("잔돈 개수 " , V )
print("동전 종류 ", coins)
print("동전 개수 ", min_coin_greedy(coins,V))

#다이나믹 프로그래밍으로 만들기 

coins = [500,400,100]
coins.sort()
V=800
def min_coin_dp(coins, V):
    dp = [0] * (V + 1)
    for i in range(1, V + 1):
        temp = 9999
        j = 0
        while j < len(coins) and i >= coins[j]:
            temp = min(dp[i-coins[j]], temp)
            j += 1
        dp[i] = temp + 1
    return dp[V]

print("잔돈 개수 " , V )
print("동전 종류 ", coins)
print("동전 개수 ", min_coin_dp(coins,V))

 

탐욕법은 큰 동전 순으로 해당 동전의 남은 값을 가지고 동전의 개수를 세지만 DP로 해결할 경우 해당 동전과 이전 해의 동전의 개수를 비교해 작은 동전 개수를 선택해 문제를 해결할 수 있습니다.