다이나믹프로그래밍 DP (=동적계획법) [문제 해결 전략]

다이나믹 프로그래밍 DP ( = 동적 계획법)

하나의 큰 문제를 여러개의 작은 문제로 나눠서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 문제 해결 법을 말한다.기억하며 풀기라고 할 수 있다.

 

출처 나무위키

다이나믹 프로그래밍은 분할정복과 비슷한데 여기서 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 후 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다음에 또 나오면 저장해둔 정답을 사용하며 속도를 향상시킨다.

 

방법론 1. 메모이제이션

배열로 -1 -1 -1 입력한 상태에서 부분적으로 답이 나오면 채워 넣는다.

이미 채워져있을 경우 그 값을 사용한다.

 

function fibbo(n)
    if memo[n] != -1           // 이미 n번째 값을 구해본 적이 있다면
        return memo[n]         // memo에 적혀있는 값을 반환해줍니다.
    if n <= 2                  // n이 2이하인 경우에는 종료 조건이므로 
        memo[n] = 1            // 해당하는 숫자를 memo에 넣어줍니다.
    else                       // 종료조건이 아닌 경우에는 
        memo[n] = fibbo(n - 1) + fibbo(n - 2)   // 점화식을 이용하여 답을 구한 뒤
                                                // 해당 값을 memo에 저장해줍니다.
    return memo[n]             // memo 값을 반환합니다.

 

방법론 2.타뷸레이션

for 문을 이용하고 배열을 순서대로 채워나가는 방식

set dp = [0, 0, 0, ...]

dp[1] = 1
dp[2] = 1

for i = 3 ... i <= n:
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[n])

 

이론적인 시간 복잡도는 같으나 하향식은 함수를 재귀적으로 여러번 시행해야하므로 타뷸레이션 접근식이 더 빠르다