다이나믹 프로그래밍

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

중복되는 연산을 처리해야 할때 주로 사용하는 알고리즘이다. 주로 점화식을 통해 해결되는 문제면 DP일 확률이 매우 높다.

즉 메모리 공간을 더 사용하여 연산 속도를 증가시킬 수 있는 방법을 다이나믹 프로그래밍, 줄여서는 DP 알고리즘 이라고 한다.

구현 - 3가지 방법

피보나치 수열 문제를 통해 3가지 구현법인 1. 재귀, 2. 탑다운, 3. 보텀업 방식에 대해서 설명하고자 한다.

1. 기본적인 피보나치 수열(n값이 작을 경우 재귀적으로 수행)

시간복잡도 : $O(2^n)$ time

def fibo(n):
    if n == 0:
        return 0
    elif n ==1 or n== 2:
        return 1
    else:
        return fibo(n-2) + fibo(n-1)

print(fibo(4)) # 출력: 3

* Memomization 기법

• 메모이제이션 : 한 번 구한 결과를 메모리 공간에 'memo'해두고 같은 식을 다시 호출하면, 결과를 그대로 가져오는 기법 (Caching 이라고 함)

• 메모이제이션 방법 : 한 번 구한 정보를 리스트와 같은 자료구조에 저장

2. memoization 기법을 활용한 피보나치 수 - TopDown 방식

d = [0] * 100 # 리스트 초기화 (한 번 구한 정보 담기 위함)
def fibo(n):
    if n ==1 or n==2: # 재귀함수 제약조건 걸어주기 
        return 1
    if d[n] != 0: # 이미 한번 계산한 값이라면 그대로 반환 
        return d[n]
    d[n] = fibo(n-2) + fibo(n-1) # 한번도 구하지 않은 값이라면 피보나치 결과 수행 
    return d[n]

print(fibo(4))

3. 반복문을 활용한 메모이제이션 기법 - BottomUp 방식

2번의 재귀로 푸는 아이디어보다 시간 복잡도가 더 빨라짐 : $O(N)$ time 소요

d = [0]* 100 # 리스트 초기화

d[1] = 1 # f(1)
d[2] = 1 # f(2)
n = 4

for i in range(3,n+1):
    d[i] = d[i-2] + d[i-1]

print(d[n])