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

📌 Dynamic Programming

복잡한 문제를 여러 개의 문제로 나누어 푸는 방법

 

필요한 계산 값을 저장해두었다가
재사용하는 알고리즘

 

 

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

피보나치 수열

피보나치 수열 점화식: F0​=0, F1​=1, Fn+2​=Fn+1​+Fn​

다음과 같이 재귀함수를 사용하여 코드를 구현할 수 있다.

def fibonacci(num):
    if num == 1 or num == 2:
        return 1
    return fibonacci(num-1) + fibonacci(num-2)

단순 재귀함수로 구현했을 때, 동일한 함수가 반복적으로 호출되는 것을 볼 수 있는데 시간복잡도가 O(2^N)으로 N값이 커짐에 따라 연산 수행시간이 기하급수적으로 늘어난다.

 

 

동적 계획법을 사용하면 이러한 반복적인 계산을 방지할 수 있다. 

수행한 결과값을 메모리에 저장해 놓고 다음에 같은 수행을 하게되면 다시 연산하지 않고 메모리에서 값을 가져와 쓴다.

1. Bottom-up 방식 (타뷸레이션)

다이나믹 프로그래밍의 전형적인 형태로, 최초 값부터 차례대로 계산해 나가는 방식 (반복문 이용)

def fibonacci(num):
    f = [0] * (num+1)
    f[1] = 1
    f[2] = 1

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

    return f[num]

 

2. Top-down 방식 (메모이제이션)

이전 계산값을 메모리에 저장하여 매번 다시 실행하지 않도록 하는 방식 (재귀함수를 이용)

def fibonacci(num):
    f = [0] * (num+1)
    f[1] = 1
    f[2] = 1

    if f[num] == 0:
        f[num] = fibonacci(num-1) + fibonacci(num-2)
        
    return f[num]

 

❗❓ DP 문제유형 확인 방법

주어진 문제를 작은 문제로 나눌 수 있는 경우 & 동일한 작은 문제들이 반복적으로 계산이 되는 경우!