[Coding Test] 8주차 - 동적계획법 1

동적계획법(DP)

동적계획법(dynamic programming)은 자주 볼 수 있는 디자인 패러다임 중에 하나입니다. 동적 계획법에서는 하나의 큰 문제를 여러 개의 작은 문제로 나눈 뒤, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용합니다.

동적계획법을 왜 사용하는 걸까요? 일반적인 재귀 방식 또한 DP와 유사하다고 볼 수 있습니다. 그러나 재귀를 단순히 사용할 시 동일한 작은 문제들이 여러 번 반복되어 비효율적으로 계산됩니다.

가장 많이 쓰이는 예시는 피보나치 수열입니다. 피보나치 수열을 재귀로 구현할 시 return f(n) = f(n-1) + f(n-2)이라는 단순한 식이 나옵니다.

이렇게 구현할 시, 위의 트리와 같은 호출이 일어납니다. 같은 값을 구하는 과정이 반복되서 일어나는 것을 확인할 수 있습니다. 그러나 DP를 이용하여 한 번 구한 작은 문제의 결과값을 저장해두고 사용하면 반복하여 계산할 필요가 없습니다.

동적계획법의 사용 조건

동적계획법의 사용 조건은 크게 두 가지입니다.

1. Overlapping Subproblems (겹치는 부분 문제): 동일한 작은 문제들이 반복해서 나타나는 경우에 사용 가능
2. Optimal Substurcture (최적 부분 구조): 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우에 사용 가능

동적계획법의 접근 방식

그럼, 문제에 동적계획법을 사용하려면 어떻게 접근해야 할까요? 이러한 방식은 Bottom-Up 방식과 Top-Down 방식으로 나뉩니다. 

Bottom-Up 방식은 아래에서부터 계산을 수행하고 값을 누적시켜서 전체 큰 문제를 해결합니다. 반복문을 사용하는 방식에 해당됩니다. 

결과값을 계산하기 위한 일차원 배열인 dp를 만들고, dp[n]이 목표로 구하는 값이라고 합시다. 그럼 Bottom-Up 방식에서는 dp[0]에서부터 시작하여 반복문을 통해 dp[n]까지 구합니다.

이와 반대로 Top-Down 방식은 큰 문제에서 작은 문제로 나눠가며, 재귀 호출을 이용해 문제를 풀게 됩니다. 

---

BOJ 동적계획법 문제

BOJ 11726 2xn 타일링

문제 요약

1. 입력: n
2. 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하기
3. 출력: 2xn 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지

풀이 과정

해당 문제에서의 점화식은 dp[n] = dp[n-1] + dp[n-2] 입니다. 또한 2x1 크기일 때의 경우의 수는 1, 2x2 크기일 때는 2이므로 dp[1] = 1, dp[2] = 2라고 볼 수 있습니다.

10,007로 나누지 않을 경우 overflow 가능성이 있기 때문에 값을 저장할 때부터 10,007로 나누어 줍니다.

코드

// BOJ 11726 2xn 타일링

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    vector<int> dp;

    cin >> n;
    dp.push_back(1);
    dp.push_back(2);

    for(int i=2; i<n; i++){
        dp.push_back((dp[i-1]+dp[i-2]) % 10007);
    }

    cout << dp[n-1];
    
    return 0;
}

BOJ 11055 가장 큰 증가하는 부분 수열

문제 요약

1. 입력: 수열 A의 크기 N, 수열 A를 이루고 있는 A_j
2. 출력: 수열 A의 합이 가장 큰 증가하는 부분 수열의 합

풀이 과정

해당 문제를 풀기 위해 dp[i]를 A[i]를 증가하는 부분 수열의 마지막 요소라고 할 때의 부분 수열의 합이라고 정의합니다. 현재 A[i]보다 앞 순서에서 A[i]보다 작은 값(A[j])이 있고, dp[j]가 dp[i]보다 크다면 dp[i]를 dp[j]로 변경해줍니다. 이렇게 for문을 돌고 난 후에 dp[i]에 현재 위치 값인 A[i]를 더해줍니다. 합이 가장 큰 부분 수열의 합을 구하기 위해서 현재 구한 dp[i]값과 이전 res 값을 비교하여 더 큰 값을 저장합니다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, A[1001], dp[1001] = {0,}, res = 0;

    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> A[i];
    }

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (A[j] < A[i])
                dp[i] = max(dp[i], dp[j]);
        }
        dp[i] += A[i];
        res = max(dp[i], res);
    }

    cout << res;

    return 0;
}

BOJ 9465 스티커

문제 요약

1. 입력: 테스트 케이스의 개수 T, n, n개의 정수
2. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 됨
3. 출력: 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값

풀이 과정

해당 문제를 풀기 위해 dp[0][i]를 윗줄 i번째 스티커를 택했을 때의 최댓값, dp[1][i]를 아랫줄 i번째 스티커를 택했을 때의 최댓값으로 정의합니다. 점화식을 세워보면 dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + dp[0][i], dp[1][i] = max(dp[0][i-1], dp[0][i-1]) + dp[1][i]라는 식이 나옵니다.

코드

// BOJ 9465 스티커

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    while (T--)
    {
        int n;
        cin >> n;
        int dp[2][100001] = {0, };
        dp[0][0] = dp[1][0] = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> dp[0][i];
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> dp[1][i];
        }

        for (int i = 2; i <= n; i++)
        {
            dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + dp[0][i];
            dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + dp[1][i];
        }

        int res = max(dp[1][n], dp[0][n]);

        cout << res << "\n";
    }

    return 0;
}

BOJ 9084 동전

문제 요약

1. 입력: 테스트 케이스의 개수 T, 동전의 가짓수 N, N가지 동전의 각 금액이 오름차순으로, 주어진 N가지 동전으로 만들어야 할 금액 M
2. 출력: N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력

풀이 과정

해당 문제를 풀기 위해 dp[i]를 i원을 만들 수 있는 방법의 수로 정의하면, dp[i] = dp[j] + dp[j-coin[i]]라는 점화식을 세울 수 있습니다.

코드

// BOJ 9084 동전

#include <iostream>
using namespace std;

int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    while (T--)
    {
        int N, M, dp[10001] = {
                      0,
                  },
                  coin[21];
        cin >> N;

        for (int i = 1; i <= N; i++)
        {
            cin >> coin[i];
        }
        cin >> M;

        dp[0] = 1;
        for (int i = 1; i <= N; i++)
        {
            for (int j = coin[i]; j <= M; j++)
            {
                dp[j] = dp[j] + dp[j - coin[i]];
            }
        }

        cout << dp[M] << "\n";
    }

    return 0;
}