[알고리즘 algorithm] 다이나믹 프로그래밍 dynamic programming 방법론, 예제

 이 글은 '파이썬 알고리즘 인터뷰'라는 책을 참고하여 작성하였습니다.

 

<다이나믹 프로그래밍>

- 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘.

- 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제, 즉 최적 부분 구조를 갖고 있는 문제를 풀이할 수 있다. 

 

<방법론>

- 타뷸레이션(Tabulation): 상향식 접근법

- 메모이제이션(Memoization): 하향식 접근법

 

ex) 피보나치 수열 코드 작성 예제

## tabulation
def fib(n):
	dp[0]=0
    dp[1]=1
   
    for i in range(2,n+1):
    	dp[i] = dp[i-1]+ dp[i-2]
    return dp[n]
    
    
## memoization
def fib(n):
    if n <= 1:
        return n
        
    if dp[n]:
    	return dp[n]
    
    dp[n] = fib(n-1)+ fib(n-2)
    return dp[n]
    
    
## minimize space
def fib(n):
	x, y = 0, 1
    for i in range(0,n):
    	x, y = y, x+y
    return n

 

+ 피보나치 수열 활용문제

leetcode.com/problems/climbing-stairs/

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <=2:
            return n
        x = 1
        y = 2
        
        for i in range(n-2):
            x, y = y, x+y
            
        return y
        

 

 

 

- ☆☆ 0-1 배낭 문제 ☆☆

en.wikipedia.org/wiki/Knapsack_problem

Knapsack problem - Wikipedia

다이나믹 프로그래밍의 대표 문제로 배낭문제가 있다. 타뷸레이션 방식으로 풀이한 코드는 다음과 같다.

def zero_one_knapsack(cargo):
    capacity = 15
    pack = []

    for i in range(len(cargo) + 1):
        pack.append([])
        for c in range(capacity + 1):
            if i == 0 or c == 0:
                pack[i].append(0)
            elif cargo[i - 1][1] <= c:
                pack[i].append(
                        max(
                            cargo[i - 1][0] + pack[i - 1][c - cargo[i - 1][1]],
                            pack[i - 1][c]))
            else:
                pack[i].append(pack[i - 1][c])

    return pack[-1][-1]

cargo = [ # cost, weight
    (4, 12),
    (2, 1),
    (10, 4),
    (1, 1),
    (2, 2),
]

r = zero_one_knapsack(cargo)
print(r)

>> 15