기초 DP 최적화

DP를 최적화 하는 방법들에 대해 알아봅시다.

 

https://anz1217.tistory.com/19

동적 계획법 (Dynamic Programming)

 

제 예전 글에서도 설명한 바 있지만, DP로 문제를 해결하는 방식과 시간복잡도 계산에 대해 다시 한번 생각해봅시다.

 

DP는 큰 문제들을 작은 부분 문제로 나누어 푸는 중, 서로 겹치는 부분 문제가 존재한다면 이를 한 번 씩만 계산하도록 Memoization하여 푸는 방식입니다.

 

요약하면 모든 문제를 많아도 1번씩만 해결하게 되므로, 일반적인 DP의 시간복잡도는 다음과 같이 나타내어지게 됩니다.

(가능한 문제의 경우의 수) \(\times\) (각 문제를 푸는데 필요한 부분 문제의 수)

 

그러면 DP의 시간복잡도를 줄이기 위해서는 어떤걸 최적화 하면 될까요?

(가능한 문제의 경우의 수) 또는 (각 문제를 푸는데 필요한 부분 문제의 수)

를 어떻게든 줄이면 되겠다는 생각을 할 수 있습니다.

---

먼저 (각 문제를 푸는데 필요한 부분 문제의 수) 부분을 한번 줄여 봅시다.

정확하게는 부분 문제의 수 자체를 줄인다기보다는, 부분 문제들의 값을 미리 계산해 놓은다음 이를 한번에 이용함으로써 큰 문제를 계산하는 시간을 줄이는 방법입니다.

 

제가 DP에 대해 뭔가 설명을 할 때나, 관련 문제를 푸는 코드들을 보면 탑다운 DP를 훨씬 많이 사용합니다.

DP점화식을 구한 상태에서 이를 코드로 바꿀 때 더 직관적이기 때문입니다.

 

하지만 앞에서 말씀드린 부분 문제들의 값을 미리 계산해 놓는다는 말은, 큰 문제를 풀기 전에 부분 문제들이 이미 풀려 있어야 한다는 것을 뜻합니다.

 

따라서 이러한 DP최적화를 할 때는 대부분 탑다운이 아닌 바텀업으로 DP를 풀게 됩니다.

 

 

 

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

21757번: 나누기

 

수열을 연속 된 네 부분으로 나누려고 합니다.

단, 각 부분은 최소 하나의 수를 포함해야 하며, 각 부분의 합은 모두 같아야 합니다.

이와 같이 수열을 나누는 경우의 수를 구해야 합니다.

 

먼저, 수열 전체의 합을 구해 봅시다. 이를 \(S\)라고 하겠습니다.

\(S\)가 4로 나누어 떨어지지 않는다면, 같은 합을 가지는 4개의 구간으로 나눌 수 없으므로, 답은 0입니다.

나누어 떨어진다면, 어디에서 구간을 나눠야 할까요?

 

수열의 누적합을 구해 봅시다.

각 구간의 수열의 원소의 합이 \(\frac S4\)이 되어야 하므로,

\(k\)번째 구간의 끝 부분은 누적합이 \(\frac S4 \times k\)가 되는 지점이 되어야 한다는 사실을 알 수 있습니다.

 

따라서 DP를 다음과 같이 정의하면,

\(DP_{k, i} : \) \(k\)번째 구간의 끝이 \(i\)번째 원소까지인 경우의 수

 

다음과 같이 점화식을 세울 수 있습니다.

\(DP_{0, 0} = 1, DP_{0, i} = 0\) (\(1 \le i \le n\)) (base case)

\(DP_{k, i} = \sum_{j=0}^{i-1} DP_{k-1,j}\) (if \(psum_i = \frac S4 \times k\))

\(DP_{k, i} = 0\) (if \(psum_i \ne \frac S4 \times k\))

 

2번째 식의 경우, DP 값을 구하기 위해 DP 테이블의 구간의 합을 구해야 합니다.

이를 원래 하던대로 하나하나 더하는 식으로 구하면 \(O(n)\)의 시간이 걸리게 됩니다.

 

하지만 DP식을 잘 보면, \(DP_{k, i}\)의 부분 문제는 모두 \(DP_{k-1, j}\)꼴임을 알 수 있습니다.

따라서 \(k\)가 증가하는 순서대로 DP값을 구해도 된다는 사실을 알 수 있습니다.

그렇게 \(DP_{k-1, i}\)를 미리 계산해 두었다고 합시다.

이 DP값들의 누적합을 구해 두면, \(DP_{k, i}\)를 구할 때, DP 테이블의 구간의 합을 \(O(1)\)에 구할 수 있게 됩니다!

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int a[100001];
ll psum[100001];
 
ll dp[5][100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        psum[i] = psum[i - 1] + a[i];
    }
 
    if (psum[n] % 4)
    {
        cout << 0;
        return 0;
    }
 
    dp[0][0] = 1;
    for (int k = 1; k <= 4; k++)
    {
        for (int i = 1; i <= n; i++)
            dp[k - 1][i] += dp[k - 1][i - 1];
 
        for (int i = 1; i <= n; i++)
        {
            if (psum[i] != psum[n] / 4 * k) continue;
            dp[k][i] = dp[k - 1][i - 1];
        }
    }
 
    cout << dp[4][n];
}

 

일반적으로 DP테이블의 구간 합이 필요할 때, 또는 DP를 계산하는데 특정한 배열의 구간합을 구해야 한다면 이와 같이 누적합을 사용하여 시간복잡도를 줄일 수 있습니다.

 

만약 구간의 합이 아니라 최소값/최대값이 필요하다면 어떨까요?

또는 DP를 계산하는데 필요한 배열의 값에 업데이트가 생긴다면?

 

그렇습니다. 세그먼트 트리를 이용해서도 DP를 최적화 할 수도 있습니다.

 

관련 문제는 생략합니다.

---

Monotone Stack/Queue를 이용한 최적화

 

Monotone Stack/Queue는 스택과 큐에 있는 원소들을 오름차순이나 내림차순으로 유지하는 방식입니다.

이를 이용해 시간복잡도를 최적화해봅시다.

 

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

17298번: 오큰수

 

수열의 각 원소 \(A_i\)에 대해, 오른쪽에 있으면서 \(A_i\)보다 큰 수 중 가장 왼쪽에 있는 수를 모두 구하라고 합니다.

이 역시 일반적인 DP로 풀려면 각 원소의 부분 문제가 \(O(n)\)개이기 때문에, 다른 방법을 생각해야 합니다.

 

스택의 원소들을 비내림차순으로 유지하면서 push해 봅시다.

만약 어떤 원소 \(A_i\)를 push했는데 비내림차순이 유지되지 않는다면, 스택의 top에 있는 원소의 오큰수가 \(A_i\)라는 것을 의미합니다.

 

총 시간복잡도 \(O(n)\)에 문제를 해결할 수 있게 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int ans[1000001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    memset(ans, -1, sizeof ans);
 
    vector <pii> stk;
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a; cin >> a;
        while (!stk.empty() && stk.back().first < a)
        {
            ans[stk.back().second] = a;
            stk.pop_back();
        }
 
        stk.push_back({ a, i });
    }
 
    for (int i = 0; i < n; i++) cout << ans[i] << ' ';
    cout << '\n';
}

 

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

11003번: 최솟값 찾기

 

\(L\)길이의 모든 구간의 최소값을 구하는 문제입니다.

물론 세그먼트 트리를 사용하여 \(O(n\log n)\)에 해결할 수도 있지만, Monotone Queue를 사용해서도 풀 수 있습니다.

(큐라고는 하지만 앞뒤에서 모두 pop이 발생할 수 있으므로, C++ deque등의 자료구조가 필요합니다)

 

큐에 원소들을 증가하는 순으로 저장해 나갑시다. 저장하는 방식은 위에서 스택을 이용한 방법과 같습니다.

여기에서 큐의 front에 \(L\)보다 이전에 있는 값이 있다면 front의 값을 pop해주면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, l;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    deque <pii> q;
 
    cin >> n >> l;
    for (int i = 0; i < n; i++)
    {
        int a; cin >> a;
        if (!q.empty() && q.front().second + l <= i) q.pop_front();
        while (!q.empty() && q.back().first >= a) q.pop_back();
        q.push_back({ a, i });
        cout << q.front().first << ' ';
    }
}

 

역시 세그트리보다 훨씬 빠른, 시간복잡도 \(O(n)\)에 문제를 해결할 수 있습니다.

---

다음으로는 (가능한 문제의 경우의 수)를 한 번 줄여봅시다.

시간복잡도가 아니라 DP의 공간복잡도를 줄이는 방법이라고 생각할 수도 있습니다.

 

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

2096번: 내려가기

 

간단한 DP인데, 메모리 제한이 파멸적입니다.

\(O(N)\)크기의 DP배열을 만들면 바로 메모리 초과를 받게 됩니다.

 

우선 DP를 다음과 같이 정의해봅시다.

\(DP_{i, j} : \) \((i,j)\)위치에 원룡이가 있을 때의 최소/최대 점수

 

\(DP_{i, j}\)를 풀기위한 부분문제를 잘 생각해보면, \(DP_{i-1, x}\)형태의 부분문제만이 필요함을 알 수 있습니다.

(또는 점화식에 따라 \(DP_{i+1, x}\) 형태)

 

결국 바텀업으로 문제를 풀어 나가면서 \(2 \times 3\)크기의 DP테이블만 유지해 나가면 문제를 풀 수 있게 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int mn_dp[2][3], mx_dp[2][3];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            swap(mn_dp[0][j], mn_dp[1][j]);
            swap(mx_dp[0][j], mx_dp[1][j]);
        }
 
        int a[3];
        cin >> a[0] >> a[1] >> a[2];
 
        mn_dp[1][0] = min(mn_dp[0][0], mn_dp[0][1]) + a[0];
        mx_dp[1][0] = max(mx_dp[0][0], mx_dp[0][1]) + a[0];
 
        mn_dp[1][1] = min(mn_dp[0][0], min(mn_dp[0][1], mn_dp[0][2])) + a[1];
        mx_dp[1][1] = max(mx_dp[0][0], max(mx_dp[0][1], mx_dp[0][2])) + a[1];
 
        mn_dp[1][2] = min(mn_dp[0][1], mn_dp[0][2]) + a[2];
        mx_dp[1][2] = max(mx_dp[0][1], mx_dp[0][2]) + a[2];
    }
 
    cout << *max_element(mx_dp[1], mx_dp[1] + 3) << ' '
        << *min_element(mn_dp[1], mn_dp[1] + 3);
}

 

 

 

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

1351번: 무한 수열

 

\(DP_i : \) \(A_i\)로 정의하면 간단히 문제를 풀 수 있을 것 같은데, 문제는 \(N\)의 범위가 너무 크다는데에 있습니다.

하지만 최대 \(10^{12}\)개의 모든 수가 DP값을 계산하는데 쓰일까요?

 

실제로 DP값을 계산하는데 필요한 총 부분문제의 개수는 \(N\)에 비해 매우 적다는 것을 알 수 있습니다.

그러면 \(10^{12}\)크기의 DP배열을 만드는 게 아니라, map등의 자료구조로 DP테이블을 구성함으로써 필요한 부분만 계산할 수 있게 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll n, p, q;
map <ll, ll> dp;
 
ll solve(ll n)
{
    if (dp.count(n)) return dp[n];
    if (n == 0) return 1;
    return dp[n] = solve(n / p) + solve(n / q);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> p >> q;
    cout << solve(n);
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

+ 요즘 많이 가입 신청이 들어오고 있습니다만, 꼭 그룹에 가입하셔서 제 문제들을 푸실 필요는 없습니다.

solved.ac 에서 태그를 찾아 푸시거나 백준 단계별로 풀기 에서 문제를 찾아 푸셔도 충분합니다!

그룹은 단순히 제 개인용 알고리즘 문제집 정리 용도이니 참고해주세요!

https://www.acmicpc.net/group/7712

ANZ1217