DP

DP(동적 계획법)

DP(Dynamic Programming)는 하나의 문제를 해결하기 위해 더 하위의 문제들로 나누어 해결하는 알고리즘 설계 기법이다.

DP는 주로 중복되는 부분 문제, 또는 최적 부분 구조의 문제에서 사용할 수 있다.

DP는 작은 하위 문제부터 시작하여 그 결과를 저장하고, 이를 이용하여 큰 문제의 해를 구한다. 이 때, 결과를 저장하여 나중에 필요할 때 값을 재사용 하는 것을 메모이제이션(Memoization) 기법이라 부른다.

DP는 따로 문제를 푸는데 필요한 공식이나 규칙이 없다. 각 문제에 상황에 맞게 DP를 사용해야 한다.

예시) 피보나치 수열

DP하면 기본적으로 떠오르는 것은 피보나치 수열이다.

피보나치 수열은

f(n) = f(n - 1) + f(n - 2)

이라는 점화식을 가지고 있다.

DP에서 중요한 점은 이러한 점화식(일반항)을 구하고, 그것을 구현하는 것이다.

DP를 사용하여 피보나치 수열의 제 n번째 수를 구하는 코드는 아래와 같다.

c++

int dp[n]; // 메모이제이션 할 배열

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    // 이미 계산한 값이 있으면 바로 반환
    if (dp[n] != -1) return dp[n];

    // 계산하지 않은 경우, 재귀 호출 후 저장
    dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return dp[n];
}

예시2) 백준 #1149 RGB거리

c++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    int rgb[1001][3];
    int r[1001];
    int g[1001];
    int b[1001];

    cin>>n; 

    for(int i = 0 ; i < n ; i++)
    {
        cin>>r[i]>>g[i]>>b[i];
    }
		//1번 집은 모두 가능
    rgb[0][0] = r[0];
    rgb[0][1] = g[0];
    rgb[0][2] = b[0];

    for(int i = 1 ; i < n ; i++)
    {
        rgb[i][0] = min(rgb[i-1][1],rgb[i-1][2]) + r[i];
        // i 번째 빨강 : i-1번째는 초록과 파랑만 가능, 아래도 마찬가지
        rgb[i][1] = min(rgb[i-1][0],rgb[i-1][2]) + g[i];
        rgb[i][2] = min(rgb[i-1][0],rgb[i-1][1]) + b[i];
    }

    cout<<min(min(rgb[n-1][0],rgb[n-1][1]),rgb[n-1][2]);
}

먼저 각 집의 rgb 비용을 r, g, b 배열에 각각 입력받는다.

2차원 배열 rgb를 선언해 주고, rgb[i]에 i 번째 집이 r, g, b 를 선택했을 때 i-1 번째 집과 색이 다른 경우 중 가능한 값인 rgb[i-1]의 0,1,2 번째 인덱스 중 최솟값과 합쳐 각각 rgb[i]의 0,1,2 번째 인덱스에 값을 넣는다.

그렇다면 배열의 마지막에 있는 세 값만 비교하여 비용의 최솟값을 구할 수 있다. 위 코드는 r은 0, g는 1, b는 2로 설정했다.

i번째의 0 인덱스에 저장할 값은 i-1번째의 1, 2 인덱스에 저장된 값중 최소와 계산해야 한다. 0번째 인덱스는 빨간색이기 때문이다.