[알고리즘] 다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 큰 문제를 작은 문제로 쪼개어 해결하는 것을 말한다. 분할정복과 다른 점은 쪼개진 작은 문제가 여러 곳에서 중복적으로 발생한다는 점이다. 따라서 같은 문제를 중복 계산하지 않고 솔루션을 공유하여 효율화하는 것이 중요하다.

 

 

Dynamic Programming 알고리즘 조건 

 

1) problem이 sub-problem으로 나누어 질 때

2) 각 sub-problem의 solution을 통해 상위 problem의 솔루션을 구할 수 있을 때

3) sub-problem들이 중복되며, 그 문제의 솔루션이 같을 때 → memoizaion

 

 

위 세 가지 조건을 충족하는 문제는 dynamic programming으로 해결할 수 있으며, 대표적인 예시로 피보나치 수열이 있다.

 

 

Top-down (재귀함수)

• 재귀식으로 해결
• 중복되는 sub-problem에 대하여 solution을 공유하지 않고, 또 다시 계산함 (따라서 DP아님)
• 시간 복잡도 $O\left(2^{n}\right)$

def fibonacci(n):
    if 1 == 0:
    	return 0
    elif n == 1:
    	return 1
    fib = fibonacci(n-1) + fibonacci(n-2)
    return fib

 

• 재귀식으로 해결하되, 중복되는 sub-problem을 저장하여 솔루션 공유 (DP)
• 시간 복잡도 0(n)

def fibonacci(n):
    store = [0, 1]
    if n < len(store):
    	return store[n]
    fib = fibonacci(n-1) + fibonacci(n-2)
    store.append(fib)
    return fib

 

 

Bottom-up (반복문)

• 시간 복잡도 0(n)
• 공간 복잡도 0(1)

def fibonacci(n):
    store = [0, 1]
    i = 2
    while True:
        if i - 1  == n:
            return store[n]
        store.append(store[i-1] + store[i-2])
        i += 1

 

---

 

[reference]

• https://www.youtube.com/watch?v=eJC2oetXaNk