동적계획법(Dynamic Programming)

DP란?

다이나믹 프로그래밍(DP)은 하나의 큰 문제를 여러 개의 작은 문제로 나누고, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 알고리즘 기법입니다. DP는 주로 최적화 문제에 사용되며, 문제를 해결하기 위한 계산량을 줄이는데 매우 유용합니다.

 

 

DP를 사용하는 이유?

일반적인 재귀(Native Recursion) 방식 또한 DP와 유사합니다. 그러나 큰 차이점은 재귀를 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적입니다.

 

ex) 피보나치 수열
피보나치수열은 각 항이 그 앞에 두 항의 합인 수열입니다. 예를 들어, 피보나치수열의 첫 10개 항은 0, 1, 1, 2, 3, 5, 8, 13...

 

 

피보나치 수를 구할 때 재귀로 구성하게 되면 f(n) = f(n-1) + f(n-2)가 됩니다. 그러나 f(n-1), f(n-2)을 구할 때 각 함수를 호출하면 동일한 값을 중복으로 구하게 되고 n의 숫자가 커질수록 함수가 호출되는 횟수도 점점 증가하게 됩니다.

 

그래서 한 번 구한 작은 문제의 결과 값을 저장하고 재사용한다면 앞에서 계산된 값을 반복할 필요가 없기 때문에 효율적으로 문제를 해결할 수 있게 됩니다!

 

1. 중복 계산 방지

동일한 작은 문제가 여러 번 반복될 때, 그 결과를 저장해 중복 계산을 피합니다.

2. 효율성

중복 계산을 줄이므로 시간 복잡도가 크게 줄어듭니다.

3. 복잡한 문제 해결

복잡한 문제를 작은 문제로 분할하여 해결할 수 있으므로, 어려운 문제도 해결할 수 있습니다.

 

사용 조건

최적 부분 구조 (Optimal Substructure)

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미합니다.

중복 부분 문제 (Overlapping Subproblems)

DP는 문제를 나누고 그 결과 값을 재활용해서 전체 답을 구하기 때문에 동일한 작은 문제들이 반복해 나타나는 경우에 사용이 가능합니다. 

 

f(1), f(2), f(3)가 반복적으로 중복이 되기 때문에 값을 재활용할 수 있습니다.

 

사용 방법

 

Top-Down 방식 (Memoization)

재귀적 접근법으로, 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출하며, 이미 계산된 하위 문제의 결과는 저장해 재사용합니다. (위에서부터 바로 호출)

 

ex) 피보나치수열 (Top-Down)

function fib(n, memo = {}) {
    if (n in memo) {
        return memo[n];
    }
    if (n <= 1) {
        return n;
    }
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

// 테스트
console.log(fib(10)); // 55

 

Bottom-Up 방식 (Tabulation)

 

반복적 접근법으로, 작은 문제부터 차례대로 해결해 나가며, 결과를 저장하고 이를 재활용하는 방식으로 큰 문제를 해결합니다. (아래에서부터 계산을 수행하고 누적시켜 큰 문제를 해결)

 

ex) 피보나치수열 (Bottom-Up)

function fib(n) {
    if (n <= 1) {
        return n;
    }
    let dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 테스트
console.log(fib(10)); // 55

 

느낀 점!

백준에서 처음 DP 문제를 접하고 머릿속이 백지가 됐다,,, 이론 없이 풀어보려 했지만 사알짝 벽을 느낀 느낌적인 느낌이다ㅜㅜ 정말 알고리즘이 중요하다는 것을 느껴서 바로 이론 공부를 시작했다! 그런데 머릿속으로는 이해가 되지만 막상 문제에 접하게 되면 DP로 풀어야 되는지부터 헷갈리기 시작하고, 점화식을 세우는 데 많은 어려움이 있었다. 앞으로 공부할 것들이 많다 힘내자!!!

<DP 문제 해결 팁>

1. 문제의 조건과 요구사항을 정확히 파악하기!
2. 문제를 작은 부분 문제들로 나눌 수 있는지 생각해 보기!
3. 부분 문제들이 어떤 관계가 있는지 파악하기!
4. 부분 문제들 간의 관계를 수학적 공식으로 표현하기!
5. 상향식(bottom-up) 또는 하향식(top-down) 접근법을 선택!

 

 

---

 

출처 🔖

https://www.acmicpc.net/problem/1463

 

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