[알고리즘] 다이나믹 프로그래밍(Dynamic Programming): DP

DP(동적 계획법)

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것. 재귀와 비슷하지만, 재귀와 다른 점은 작은 문제들을 여러번 반복하지 않아 비효율적인 계산을 하지 않아도 된다는 것이다.

 

DP의 사용 조건

1. Overlapping Subproblems(겹치는 부분적인 문제)

DP는 기본적으로 문제를 나누고 그 작은 문제들의 결과값을 재활용한다. 즉 동일한 작은 문제로 나눌 수 있어야 한다.

ex) 피보나치 수열 —> f(n) = f(n - 1) + f(n - 2)

 

2. Optimal Substructure(최적 부분 구조)

부분 문제의 최적 결과값을 이용해 전체 문제의 최적 결과값을 구할 수 있어야 한다.

위 그림에서 A → X의 최단경로는 AX2이고 X → B의 최단경로는 BX2이다. 다른 경로를 택한다 해서 전체 최단 경로가 변하지 않는다. 즉 이전의 계산 값을 그대로 사용해도 전체 결과의 값을 그대로 구할 수 있는 것이다.

 

DP사용하기

1. DP로 풀 수 있는 문제인지 파악

 

2. 문제의 변수 파악

   문제에서 몇 개의 변수를, 어떤 것을 변수로 사용해야 할지 정해야 한다.

   예를 들어 피보나치 수열에서는 n이 변수이고, 차이(edit)는 1로 두어야 한다.

 

3. 변수 간 관계식 만들기(점화식)

 

4. 메모하기

   변수 값에 따른 결과를 저장할 배열을 미리 만들고 그 결과가 나올 때마다 배열 내에 저장, 해당 값을 재사용

 

5. 기저 상태 파악

   f(0), f(1) → 제일 낮은 상태의 값을 파악

 

6. 구현

• top-down
  • 재귀 사용. 위에 n부터 시작해 1이 될때까지 실행
• bottom-up
  • 반복문을 사용해 1부터 시작해 n이 될때까지 실행

Memoization

동적 프로그래밍은 작은 문제들이 반복되고 그 값들이 항상 같다. 따라서 이 작은 값들을 저장해두고 나중에 다시 사용하는 것을 memoization이라고 한다.  

 

ex) 조합

조합(combination)을 쓸 때 중복되는 계산이 너무 많이 일어난다. 즉 값을 알고 있는 것은 array에 넣어서 바로 구할 수 있도록 처리할 수 있다. 

#include <iostream>
#include <vector>

using namespace std;

#define MAX 100 // MAX값은 필요에 따라 조정 가능

int dp[MAX+1][MAX+1];

int combination(int n, int r) {
    if (dp[n][r]) return dp[n][r]; // 이미 계산된 값이 있다면 재사용
    if (n == r || r == 0) return dp[n][r] = 1; // 기저 조건

    // 조합의 성질을 이용: nCk = (n-1)C(k-1) + (n-1)Ck
    return dp[n][r] = combination(n - 1, r - 1) + combination(n - 1, r);
}

int main() {
    int n, k;
    cin >> n >> k; // n과 k를 입력받음

    cout << combination(n, k) << endl; // nCk를 출력

    return 0;
}