[PART2]CH.08_다이나믹 프로그래밍

- 다이나믹 프로그래밍

 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 다이나믹 프로그래밍(Dynamic Programming) 기법으로 동적 계획법이라고 표현하기도 한다.

 

피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 이러한 문제는 다이나믹 프록래밍을 사용하면 효율적으로 해결할 수 있다. 다만 항상 다이나믹 프로그래밍을 사용할 수 없으며, 다음 조건을 만족할 때 사용할 수 있다. 

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 이러한 조건을 만족하는 대표 문제이다. 이 문제를 메모이제이션(Memoization)기법을 사용해서 효율적으로 해결할 수 있다. 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱Caching이라고도 한다. 

 

#코드(2가지 방식 결과는 모두 같다.)

def fibo_dp1(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]    
    d[x] = fibo_dp1(x-1) + fibo_dp1(x-2)
    return d[x]
 
def fibo_dp2(n):
    cache = [0 for _ in range(n+1)]
    cache[0] = 0
    cache[1] = 1
    
    for i in range(2, n+1):
        cache[i] = cache[i-1] + cache[i-2]
    return cache[n]
 
if __name__ == "__main__":
    d = [0]*100
    print(fibo_dp1(6))
    print(fibo_dp2(6))
 
 
 
 
 

 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘이다. 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해겨한다는 점이 특징이다. 그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것이다.

시간 복잡도는 O(N)이다. 이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 쿤 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down) 방식이라고 말한다. 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업(Bottom-Up) 방식이라고 한다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.

 

실전문제

 

• 1로 만들기

#코드

import sys
 
def dp(x):
    dp_table = [0]*30010
 
    for i in range(2, x+1):
        dp_table[i] = dp_table[i-1] +1
        if i%2==0:
            dp_table[i] = min(dp_table[i], dp_table[i//2]+1)
        if i%3==0:
            dp_table[i] = min(dp_table[i], dp_table[i//3]+1)
        if i%5==0:
            dp_table[i] = min(dp_table[i], dp_table[i//5]+1)
    return dp_table[x]
 
 
if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    print(dp(n))

 

실전문제

 

• 개미 전사

#코드

import sys
 
def dp(x):
    global arr
    dp_table = [0]*110
 
    dp_table[0] = arr[0]
    dp_table[1] = max(arr[0], arr[1])
    for i in range(2, x):
        dp_table[i] = max(dp_table[i-1], dp_table[i-2]+arr[i])     
    return dp_table[x-1]
 
 
if __name__ == "__main__":
    input = sys.stdin.readline
    n   = int(input())
    arr = list(map(int, input().split())) 
    print(dp(n))

 

실전문제

 

• 바닥 공사

#코드

import sys
 
def dp(x):
    dp_table = [0]*1001
    
    dp_table[1] = 1
    dp_table[2] = 3
 
    for i in range(3, n+1):
        dp_table[i] = (dp_table[i-1]+dp_table[i-2]*2)%796796 
 
    return dp_table[x]
 
 
if __name__ == "__main__":
    input = sys.stdin.readline
    n   = int(input())
    print(dp(n))
 
 
 
 

 

실전문제

 

• 효율적인 화폐 구성

#코드

import sys
 
def dp():
    global n, m, arr
 
    dp_table = [10001]*(m+1)    
    dp_table[0] = 0
 
    for i in range(n):
        for j in range(arr[i], m+1):           
            dp_table[j] = min(dp_table[j], dp_table[j-arr[i]]+1)
     
    if dp_table[m] == 10001:
        print(-1)
    else:
        print(dp_table[m])
    
 
 
if __name__ == "__main__":
    input = sys.stdin.readline
    n, m  = map(int, input().split())
    arr   = []
 
    for i in range(n):
        arr.append(int(input()))
 
    dp()