동적 계획법(DP, Dynamic Programming)

이전에 계산한 값을 재사용하여, 하나의 문제를 한 번만 풀게 하는 알고리즘 패러다임

DP는 Divide & Conquer와 비슷하지만, 중간 결과를 저장하여 효율성을 높인다는 점에서 차이

이전에 계산해둔 값을 메모리(배열 등)에 저장해서 반복 작업을 줄이는 기법이 핵심

• 하위 문제의 결과를 먼저 저장하고, 이를 나중에 필요할 때 사용

• Tabulation(bottom-up), Memoization(top-down)

Top-Down DP

• 가장 큰 문제부터 풀기 시작하여, 작은 문제들을 재귀적으로 호출하여 답을 구하는 방식

• 주로 재귀를 통해 해결하고, 이때 메모이제이션(Memoization)을 활용하여 복잡도를 줄임

Bottom-Up DP

• 작은 문제들을 먼저 풀기 시작하여, 최종적으로 가장 큰 문제들을 해결하는 방식

• 주로 반복문을 통해 해결하고, 점화식과 기저 사례(base case)가 필요 → tabulation

for (int i = 2;i <= 40; ++1) {
	dp[i] = dp[i-1] + dp[i-2];
}

int fibo(int n) {
	if (n <= 2) return 1; // base case
    int &ret = dp[n]; // 
    // 이미 구한 값이라면 바로 사용
    if (ret != -1) return ret;
    return ret = fibo(n-1) + fibo(n-2);
}

동적 계획법을 사용하는 조건

두 가지 속성을 만족해야 동적 계획법으로 문제를 해결할 수 있음

겹치는 부분(작은) 문제(Overlapping Subproblem)

• 어떠한 문제가 여러 개의 부분(하위) 문제(subproblem)으로 쪼갤 수 있을 때 사용

최적 부분 구조(Optimal Substructure)

• 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 사용

예시: $N$번째 피보나치 수를 구하는 문제
N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제(하위 문제)로 쪼갤 수 있음
문제의 정답을 하위 문제의 정답을 합하는 것으로 구할 수 있음

피보나치 수열 - 재귀

피보나치 수열을 재귀로 구현할 시 발생하는 문제점

• 재귀함수를 통해 호출하게 되면, 이미 구했던 값도 다시 계산해야 하기 때문에

• 시간 초과 발생 및 stack overflow 가능성 존재

int fibo(int N) {
	if (N <= 2) return 1;
    return fibo(N-1) + fibo(N-2);
}

피보나치 수열 - 반복문

dp[2] = dp[1] = 1 // 1부터 시작하고 조항이 0이라 가정
for (int i = 3; i <= n; ++i) {
	dp[i] = dp[i-1] + dp[i-2]; // 점화식
}

피보나치 수열을 재귀 함수로 구현하면 시간 복잡도는 $O(2^N)$
단순 반복문으로 구현하면 시간 복잡도는 $O(N)$
점화식: $a_i = a_{i-1} + a_{i-2}$
단, 갱신 순서에 유의