[Python] 동적 계획법 (Dynamic Programming)

1. DP (Dynamic Programming) 란?

복잡한 문제를 여러 개의 작은 부분 문제 (Sub-Problem)로 나누어 해결하는 방법 !

(작은 문제에서 구한 답을 다시 그것을 포함하는 큰 문제에서 사용)

한번 계산한 문제는 다시 계산하지 않도록 하는 방법 !

 

대표적인 예시로 피보나치 수열이 있습니다.

피보나치 수열은 N번째의 값 = N-1 번째의 값 + N-2 번째의 값을 계산하는 수열입니다.

위 그림처럼 분할하여 답을 구하는데, 중간에 중복 호출이 발생하기 떄문에 Memoization 기법을 사용합니다.

 

Memoization 이란?

프로그래밍 할 때, 반복되는 결과를 메모리에 저장하여 중복호출 되었을 때, 한 번 더 계산하지 않고 메모리에 저장되어 있는 것을 가져와서 재활용 하는 기법 입니다.

장점으로 속도가 빨라지지만 단점으론 메모리를 차지하게 됩니다. 즉, 실행 시간과 메모리를 교환하는 느낌입니다.

---

Top-Down 방식

d = [0] * 100
def fib(n):
    if n==1 or n==2:
    	return 1
    if d[n] != 0:
    	return d[n]
    d[n] = fib(n-1) + fib(n-2)   	
    return d[n]

Top-Down 방식은 메모제이션 기법을 사용하여 다이나믹 프로그래밍을 구현하는 방식 중 하나입니다.

큰 문제를 해결하기 위해 작은 문제를 호출하는 것입니다.

주로 사전(Dictionary) 자료형을 이용할 수 있는데, 주로 수열처럼 연속적이지 않은 자료가 주어질 떄 유용하고 속도도 매우 빠릅니다.

하지만, 재귀함수를 반복적으로 사용하기 때문에 함수 호출에 대한 오버헤드가 발생합니다.

 

Bottom-Up 방식

def fib(n):    
    n_0, n_1 = 0, 1
    for _ in range(n):
        n_0, n_1 = n_1, n_0 + n_1    
    return n_0

Bottom-Up 방식은 타블레이션(tabulation)을 사용하여 다이나믹 프로그래밍을 구현하는 방식 중 하나입니다.

타블레이션이란 하위 문제부터 천천히 해결하면서 더 큰 문제를 해결하는 기법을 말합니다.

재귀함수를 사용하지 않고 작은 문제부터 답을 도출하여 큰 문제를 해결하는 Bottom-Up 방식입니다.

모든 부분 문제를 해결해야하는 단점이 있지만, 자유로워 시간 및 메모리의 최적화가 쉽습니다.

 

---

참고

 

https://doing7.tistory.com/75?category=857313 

[알고리즘] 다이나믹 프로그래밍 with Python

https://do-rang.tistory.com/9

[알고리즘] Dynamic Programming (동적 계획법)