단조 큐 최적화 (Monotone Queue Optimization)

정의

단조 큐 최적화 (Monotone Queue Optimization) 는 DP 전이 dp[i] = min/max_{j ∈ window(i)} f(j) + g(i) 에서, 전이 후보 j 의 집합 이 슬라이딩 윈도우 를 이루고 f(j) 가 결합된 값이 단조 일 때, monotonic deque 로 후보 집합을 O(1) amortized 에 유지해 DP 전체를 O(N) 으로 가속하는 기법.

슬라이딩 윈도우 의 최댓값/최솟값 구하기 기본 패턴이 그대로 DP 에 들어간다. Deque Trick 의 일반화.

문제 상황과 동기

DP 전이가 다음과 같다고 하자.

dp[i] = max_{j ∈ [i - K, i - 1]} (dp[j] + value[i])

• naive: 매 i 마다 윈도우 K 개 후보 다 봄. O(N · K).
• monotone deque: 후보 deque 에 유효한 j 만 유지. 한 j 가 deque 에 한 번 push, 한 번 pop. O(N) amortized.

핵심 통찰: dp[j_1] ≤ dp[j_2] 이고 j_1 < j_2 이면 j_1 은 영원히 무용지물. 새로 들어오는 i 에 대해 j_2 가 항상 후보로 더 좋다 (또는 같다). 그래서 deque 에는 DP 값이 단조 감소 인 인덱스만 남긴다.

시각화

핵심 아이디어

deque 안의 인덱스: j_1 < j_2 < ... < j_k
이들의 DP 값: dp[j_1] > dp[j_2] > ... > dp[j_k]   (max 최적화)

새 인덱스 i 추가:
  while deque.back() 의 dp 값 ≤ dp[i]: pop_back
  push_back(i)

윈도우 밖 인덱스 제거:
  while deque.front() < i - K: pop_front

답:
  dp[i] = dp[deque.front()] + value[i]

각 인덱스가 deque 에 한 번 push, 한 번 pop. 총 O(N).

알고리즘

monotone_queue_dp(N, K, value):
    dp[0] = 0
    deque = [0]
    for i = 1..N:
        # 윈도우 밖 제거
        while deque.front() < i - K:
            deque.pop_front()
        # 답
        dp[i] = dp[deque.front()] + value[i]
        # 새 후보 추가 (단조 유지)
        while deque is not empty and dp[deque.back()] ≤ dp[i]:
            deque.pop_back()
        deque.push_back(i)
    return dp[N]

구현

// 길이 K 윈도우의 max DP, O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k; cin >> n >> k;
  vector<long long> v(n + 1), dp(n + 1, 0);
  for (int i = 1; i <= n; i++) cin >> v[i];
  deque<int> dq;
  dq.push_back(0);
  for (int i = 1; i <= n; i++) {
      while (!dq.empty() && dq.front() < i - k) dq.pop_front();
      dp[i] = dp[dq.front()] + v[i];
      while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
      dq.push_back(i);
  }
  cout << dp[n] << "\n";
}

# 길이 K 윈도우 max DP, monotonic deque
from collections import deque
import sys
input = sys.stdin.readline
​
n, k = map(int, input().split())
v = [0] + list(map(int, input().split()))
dp = [0] * (n + 1)
dq = deque([0])
for i in range(1, n + 1):
  while dq and dq[0] < i - k:
      dq.popleft()
  dp[i] = dp[dq[0]] + v[i]
  while dq and dp[dq[-1]] <= dp[i]:
      dq.pop()
  dq.append(i)
print(dp[n])

// 길이 K 윈도우 max DP
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken());
      long[] v = new long[n + 1], dp = new long[n + 1];
      st = new StringTokenizer(br.readLine());
      for (int i = 1; i <= n; i++) v[i] = Long.parseLong(st.nextToken());
      Deque<Integer> dq = new ArrayDeque<>();
      dq.addLast(0);
      for (int i = 1; i <= n; i++) {
          while (!dq.isEmpty() && dq.peekFirst() < i - k) dq.pollFirst();
          dp[i] = dp[dq.peekFirst()] + v[i];
          while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
          dq.addLast(i);
      }
      System.out.println(dp[n]);
  }
}

5 2
3 1 4 1 5

13

(5 칸, 한 번에 최대 2 칸 점프. 각 칸의 값을 더해 최대화. 답 = 3+4+1+5 = 13)

복잡도

각 원소가 deque 에 한 번 push, 한 번 pop → 총 O(N).

변형 / 활용

함정

1. 같은 값의 비교

dp[deque.back()] ≤ dp[i] 와 dp[deque.back()] < dp[i] 의 차이가 답에 영향. 같은 값 도 pop 하는 것이 일반적.

2. 윈도우 정의

[i - K, i - 1] 와 [i - K + 1, i] 의 인덱싱 차이. 문제 정의에 맞춰 front 제거 조건 을 정확히.

3. min 과 max 의 대칭

max 최적화는 단조 감소 deque, min 최적화는 단조 증가 deque. 부등호 방향 헷갈리지 않게.

4. 음수 / 0 처리

value[i] 가 음수면 작은 j 가 더 좋을 수도. DP 정의를 다시 점검.

CHT 와의 관계

Convex Hull Trick 은 선형식 m·x + b 들의 lower/upper envelope. monotone queue 는 일반적인 어떤 함수 값 의 monotone 후보. CHT 는 monotone queue 의 추가 기하 구조 + 이분 탐색 변형.

BOJ 연습 문제

참고

• 덱 트릭
• 슬라이딩 윈도우
• Convex Hull Trick
• 크누스 최적화
• DnC DP 최적화