덱 DP (슬라이딩 윈도우 최적화)

정의

덱 DP (Deque DP) 는 점화식 dp[i] = min/max_{j in [i-k, i-1]} (dp[j] + cost(i,j)) 꼴에서 monotonic deque 를 써서 최적 j 후보를 O(N) 에 유지하는 기법. 슬라이딩 윈도우 최댓값/최솟값의 일반화로, 윈도우 내에서 비용까지 포함한 최적 인덱스 를 관리한다.

문제 상황과 동기

dp[i] = max(dp[j] + a[j]) for j < i and i - j <= K. Naive 하면 각 i 에서 K 개 순회 -> O(NK). N=10^6, K=10^5 면 10^11.

핵심 통찰: 윈도우 안의 후보 중 dp[j] + something 이 최대인 j 만 deque 에 유지. 더 이상 최적이 될 수 없는 후보는 pop.

시각화

핵심 아이디어

DP: dp[i] = best(dp[j] + a[i])  for j in [i-K, i-1]
    where best = maximal computed value

Deque invariant:
  1. Index range: front is always within [i-K, i-1]
  2. Value order: dp[deque[0]] >= dp[deque[1]] >= ... (decreasing)
  3. Old index from front when out of range
  4. New candidate deletes from back if inferior

Deque 에는 인덱스 만 저장. dp[deque.front()] 이 항상 현재 i 에 대한 최적값.

알고리즘

deque dq
for i = 0..N-1:
    # 1. 만료된 front 제거
    while dq not empty and dq.front() < i - K:
        dq.pop_front()

    # 2. 현재 dp[i] 계산
    if dq empty:
        dp[i] = a[i]
    else:
        dp[i] = dp[dq.front()] + a[i]

    # 3. dq.back() 이 dp[i] 보다 나쁘면 제거
    while dq not empty and dp[dq.back()] <= dp[i]:
        dq.pop_back()

    # 4. 현재 i 를 후보에 추가
    dq.push_back(i)

구현

// Maximum sum subsequence: pick elements at distance <= K
// dp[i] = max sum ending at i, each pair distance ≤ K
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k; cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<long long> dp(n);
  deque<int> dq;
  long long ans = 0;
  for (int i = 0; i < n; i++) {
      while (!dq.empty() && dq.front() < i - k)
          dq.pop_front();
      dp[i] = a[i];
      if (!dq.empty()) dp[i] += dp[dq.front()];
      while (!dq.empty() && dp[dq.back()] <= dp[i])
          dq.pop_back();
      dq.push_back(i);
      ans = max(ans, dp[i]);
  }
  cout << ans << "\n";
  return 0;
}

from collections import deque
import sys
input = sys.stdin.readline
​
n, k = map(int, input().split())
a = list(map(int, input().split()))
dp = [0] * n
dq = deque()
ans = 0
for i in range(n):
  while dq and dq[0] < i - k:
      dq.popleft()
  dp[i] = a[i]
  if dq:
      dp[i] += dp[dq[0]]
  while dq and dp[dq[-1]] <= dp[i]:
      dq.pop()
  dq.append(i)
  ans = max(ans, dp[i])
print(ans)

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());
      int[] a = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
      long[] dp = new long[n];
      Deque<Integer> dq = new ArrayDeque<>();
      long ans = 0;
      for (int i = 0; i < n; i++) {
          while (!dq.isEmpty() && dq.peekFirst() < i - k)
              dq.pollFirst();
          dp[i] = a[i];
          if (!dq.isEmpty()) dp[i] += dp[dq.peekFirst()];
          while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i])
              dq.pollLast();
          dq.offerLast(i);
          ans = Math.max(ans, dp[i]);
      }
      System.out.println(ans);
  }
}

8 3
1 -3 5 -2 8 -1 4 -6

13

5 2
-5 -1 -3 -2 -4

-1

복잡도

변형 / 활용

널리 사용되는 예: BOJ 11003 (최솟값 찾기), BOJ 2096 (내려가기, 슬라이딩 윈도우 DP).

함정

1. 부등호 방향

최댓값: dp[dq.back()] <= dp[i] 이면 pop. 최솟값: >= 로 반대. 혼동하지 않도록.

2. 초기 K 값

i < K 일 때는 윈도우가 충분히 크지 않음. i - k 가 음수가 되지 않도록 조건.

3. 0-1 범위 반영

dp[i] 가 기본값 a[i] (단독 선택) 인지, 아니면 이전 dp 값과 합쳐야 하는지. 문제 정의에 따라.

BOJ 연습 문제

참고

• 동적 계획법
• 슬라이딩 윈도우
• 두 포인터
• 세그먼트 트리 (대안: range minimum query)