단조 큐를 통한 동적 계획법 최적화 개요

단조 큐는 특정 조건 하에서 무의미한 후보를 빠르게 제거함으로써 상태 전이의 효율을 높이는 강력한 기법이다. 특히, 결정의 범위가 항상 증가하거나 감소하는 경우, 즉 윈도우 크기가 고정되거나 단조롭게 변할 때 효과적이다. 이는 일반적으로 슬라이딩 윈도우 문제로 모델링 가능하며, 대부분의 최적화 패턴은 이 구조에 근거한다.

핵심 원리는 다음과 같다:

• 최솟값을 찾고자 한다면, 오름차순 정렬된 큐 유지
• 최댓값을 찾고자 한다면, 내림차순 정렬된 큐 유지
• 큐의 머리(앞)는 항상 윈도우 내 최적의 선택지

일반적인 구현 틀 (피어코드)

입력 데이터 처리
각 상태에 대해 반복:
    윈도우 밖의 요소 제거 (불법 상태)
    현재 상태의 값 갱신
    큐의 단조성 유지: 꼬리에서 불필요한 요소 제거
    현재 상태를 큐에 삽입

대표적인 응용 예제

1. 최대 연속 부분합 (최대 하위 배열 합)

배열의 연속 부분합 중 최댓값을 찾는 문제. 전처리로 prefix sum를 사용하고, 각 위치에서 이전에 등장한 가장 작은 전치합을 단조 큐로 관리한다.

#include <bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;

int n, m, a[N], sum[N], q[N], h, t, ans = -LLONG_MAX;

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }

    for (int i = 1; i <= n; ++i) {
        // 윈도우 범위 밖 요소 제거
        while (h <= t && i - q[h] > m) h++;
        // 최적해 갱신: 현재 합 - 최소 과거 합
        ans = max(ans, sum[i] - sum[q[h]]);
        // 단조 오름차순 유지: 꼬리에서 큰 값 제거
        while (h <= t && sum[q[t]] >= sum[i]) t--;
        q[++t] = i;
    }
    cout << ans << endl;
    return 0;
}

2. 펜스 칠하기 (Fence Painting)

각 작업자가 특정 판재를 포함해야 하는 구간을 칠하는 문제. f[i][j]는 첫 i명의 작업자가 처음 j개 판재를 칠했을 때의 최대 수익.

특히, 작업자가 시작점 또는 끝점만 설정 가능한 경우를 분리하여 처리하며, 단조 큐로 시작점 가치를 유지한다.

#include <bits/stdc++.h>
#define N 100010
#define M 110
using namespace std;

int n, m, f[M][N];
struct Worker { int l, p, s; } w[N];

bool cmp(const Worker& a, const Worker& b) {
    return a.s < b.s;
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> w[i].l >> w[i].p >> w[i].s;
    sort(w+1, w+m+1, cmp);

    for (int i = 1; i <= m; ++i) {
        int h = 0, t = 0;
        int L = w[i].l, P = w[i].p, S = w[i].s;
        for (int j = 0; j <= n; ++j) {
            f[i][j] = f[i-1][j]; // 작업자 미사용
            if (j) f[i][j] = max(f[i][j], f[i][j-1]); // 현재 판재 미칠 수 없음

            // 윈도우 외부 요소 제거
            if (h <= t && q[h] < j - L) h++;

            // j >= S: 끝점으로만 가능
            if (j >= S && h <= t) {
                int k = q[h];
                f[i][j] = max(f[i][j], f[i-1][k] + P * (j - k));
            }

            // j < S: 시작점으로만 가능
            if (j < S) {
                while (h <= t && f[i-1][q[t]] - q[t]*P <= f[i-1][j] - j*P)
                    t--;
                q[++t] = j;
            }
        }
    }
    cout << f[m][n] << endl;
    return 0;
}

3. P1725 - 치루노의 도약

현재 위치 i는 [i-R, i-L] 범위에서 올 수 있음. 이를 슬라이딩 윈도우로 보고, f[k] 값을 기준으로 단조 감소 큐를 유지하여 최적 전이를 빠르게 찾는다.

#include <bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;

int n, L, R, a[N], f[N], q[N], h, t, ans = -LLONG_MAX;

signed main() {
    cin >> n >> L >> R;
    for (int i = 0; i <= n; ++i) cin >> a[i];
    memset(f, -127, sizeof(f));
    f[0] = 0;

    for (int i = L; i <= n; ++i) {
        // 새 후보 추가: f[i-L]를 큐에 넣기 전에 단조성 유지
        while (h <= t && f[q[t]] <= f[i-L]) t--;
        q[++t] = i - L;

        // 윈도우 범위 밖 제거
        while (h <= t && q[h] < i - R) h++;

        f[i] = f[q[h]] + a[i];

        // 답 후보 확인
        if (i > n - R) ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

4. 1599: [예제 3] 잔디 깎기 (Mowing the Lawn)

연속 k+1 마리의 소 중 적어도 하나는 선택하지 않아야 함. 이는 f[i] = i번째 소를 선택하지 않았을 때까지의 최소 효율을 의미.

결과적으로, f[i]는 f[q[h]] + a[i] 형태로 전이되며, 단조 증가 큐를 통해 윈도우 내 최소값을 빠르게 얻는다.

#include <bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;

int n, m, a[N], sum, f[N], q[N], h, t, min_val = LLONG_MAX;

signed main() {
    cin >> n >> m;
    m++;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
    }

    for (int i = 1; i <= n; ++i) {
        while (h <= t && f[q[t]] >= f[i-1]) t--;
        q[++t] = i - 1;
        while (h <= t && q[h] < i - m) h++;
        f[i] = f[q[h]] + a[i];
        if (i > n - m) min_val = min(min_val, f[i]);
    }
    cout << sum - min_val << endl;
    return 0;
}

5. 1600: [예제 4] 여행 문제 (Travel Problem)

원형 경로를 선형화하여 두 번 탐색. 각 방향에 대해 전위합을 계산하고, 단조 증가 큐를 통해 음수 발생 여부 판단.

#include <bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;

int n, s[N<<1], ans[N], h, t, p[N], d[N], a[N<<1], q[N];

signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> p[i] >> d[i];
    d[0] = d[n];
    for (int i = 1; i <= n; ++i) a[i] = a[i+n] = p[i] - d[i];

    // 순방향 탐색
    for (int i = 1; i < (n<<1); ++i) s[i] = s[i-1] + a[i];
    h = 1; t = 0;
    for (int i = 1; i < (n<<1); ++i) {
        while (h <= t && s[q[t]] >= s[i]) t--;
        q[++t] = i;
        while (h <= t && q[h] <= i - n) h++;
        if (i >= n && s[q[h]] >= s[i-n]) ans[i-n+1] = 1;
    }

    // 역방향 탐색
    for (int i = 1; i <= n; ++i) a[i] = a[i+n] = p[n-i+1] - d[n-i];
    for (int i = 1; i < (n<<1); ++i) s[i] = s[i-1] + a[i];
    h = 1; t = 0;
    for (int i = 1; i < (n<<1); ++i) {
        while (h <= t && s[q[t]] >= s[i]) t--;
        q[++t] = i;
        while (h <= t && q[h] <= i - n) h++;
        if (i >= n && s[q[h]] >= s[i-n]) ans[(n<<1)-i] = 1;
    }

    for (int i = 1; i <= n; ++i)
        cout << (ans[i] ? "TAK" : "NIE") << '\n';
    return 0;
}

단조 큐 최적화 다중 배낭 문제

기본 다중 배낭은 O(nms)지만, 단조 큐를 활용하면 O(nm)로 줄일 수 있다. 핵심은 v로 나눈 나머지별로 그룹화하고, 각 그룹 내에서 슬라이딩 윈도우처럼 처리하는 것.

모든 상태는 f[i] = max(f[j] + w * ((i-j)/v)) 형태로 전이되며, j ≡ i mod v인 경우만 고려.

#include <bits/stdc++.h>
#define int long long
#define N 40100
using namespace std;

int n, W, ans, g[N], f[N], q[N], num[N];

signed main() {
    cin >> n >> W;
    for (int i = 1; i <= n; ++i) {
        memcpy(f, g, sizeof(g));
        int v, w, m;
        cin >> w >> v >> m;
        if (v == 0) { ans += m * w; continue; }

        for (int r = 0; r < v; ++r) {
            int h = 1, t = 0;
            for (int k = r; k <= W; k += v) {
                while (h <= t && q[h] < k - m*v) h++;
                while (h <= t && f[k] >= f[q[t]] + (k - q[t])/v * w) t--;
                q[++t] = k;
                g[k] = max(f[k], f[q[h]] + (k - q[h])/v * w);
            }
        }
    }
    cout << g[W] + ans << endl;
    return 0;
}

다른 알고리즘과의 복합 적용

P3957 [NOIP2017] 점프하우스 (Jumping House)

이분 탐색 + 동적 계획법 + 단조 큐 최적화의 복합 문제. 목표 점수를 만족하면서 최소 거리 이동을 구해야 함.

check(g) 함수 내에서, b[i]-d-g ≤ b[k] ≤ b[i]-d+g 범위 내의 전이만 허용. 단조 감소 큐로 최대 점수 유지.

#include <bits/stdc++.h>
#define int long long
#define INF LLONG_MAX
using namespace std;

const int N = 1000100;
int n, d, m, f[N], a[N], b[N], q[N], sum;

bool check(int g) {
    memset(f, -0x3f, sizeof(f));
    int h = 0, t = -1, R = 0;
    f[0] = 0;

    for (int i = 1; i <= n; ++i) {
        // 새로운 후보 추가: R이 현재 인덱스보다 작고, 거리 제한 내
        while (R < i && b[R] <= b[i] - d + g) {
            while (h <= t && f[q[t]] <= f[R]) t--;
            q[++t] = R++;
        }
        // 윈도우 내에 없는 요소 제거
        while (h <= t && (b[q[h]] < b[i] - d - g || b[q[h]] > b[i] - d + g)) h++;
        if (h <= t) f[i] = f[q[h]] + a[i];
        if (f[i] >= m) return true;
    }
    return false;
}

signed main() {
    cin >> n >> d >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> b[i] >> a[i];
        if (a[i] > 0) sum += a[i];
    }
    if (sum < m) { puts("-1"); return 0; }

    int l = 0, r = b[n];
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}