덱 활용 구간 최댓값 트릭 (Monotonic Deque Trick)

정의

덱 트릭 (Deque Trick) 은 덱 (double-ended queue) 에 원소의 인덱스를 단조로운 값 순서 로 유지해, 슬라이딩 윈도우의 최댓값 또는 최솟값을 O(N) 에 구하거나, DP 전이에서 일정 범위의 후보 최적값을 O(1) amortized 로 찾는 최적화 기법.

문제 상황과 동기

슬라이딩 윈도우 최댓값

크기 K 인 슬라이딩 윈도우가 배열을 지나갈 때, 각 위치에서의 최댓값을 Q 번 묻는다.

• naive: 매 윈도우마다 K 개 순회. O(NK). N=10^6, K=10^5 면 10^11.
• deque trick: 각 원소가 덱에 push/pop 되는 횟수 합 = O(N). 전체 O(N).

핵심 통찰: 새로 들어온 값보다 작은 (최댓값 기준) 값들은 앞으로 절대 최댓값이 될 수 없으므로 덱에서 제거해도 안전하다. 윈도우를 벗어난 값도 제거한다. 이렇게 하면 덱은 항상 내림차순 (최댓값 기준) 이 유지된다.

DP 최적화

다음 형태의 DP 에서 사용한다.

dp[i] = max / min (dp[j] + cost(j, i))   (i - K <= j < i)

여기서 cost(j, i) 가 j 만의 함수 + i 만의 함수 로 분리 가능하고 (cost(j, i) = A[j] + B[i]), 슬라이딩 윈도우 제약이 있을 때, dp[j] + A[j] 를 단조 감소/증가 덱으로 관리하면 O(1) 에 최적 후보를 찾는다.

시각화

핵심 아이디어

덱은 항상 값에 대해 단조 (최댓값이면 내림차순, 최솟값이면 오름차순) 이다.

슬라이딩 윈도우 최댓값
  deque: [인덱스 ...]  (값 a[index] 는 내림차순)
  invariant:
    - 덱 앞: 현재 윈도우에서 가장 큰 값의 인덱스
    - 덱 뒤: 방금 들어온 값의 인덱스 (가장 작은 값)

  push(i):
    1. dq.front() <= i - K -> dq.pop_front()     # 윈도우 이탈
    2. a[dq.back()] <= a[i] -> dq.pop_back()      # 불필요한 후보 제거
    3. dq.push_back(i)

  query_max(): return a[dq.front()]

amortized O(N) 인 이유: 각 원소는 정확히 한 번 push, 최대 한 번 pop_front, 최대 한 번 pop_back. 총 연산 = O(N).

알고리즘

SlidingWindowMax(a[0..N-1], K):
    dq = empty deque
    result = []
    for i = 0..N-1:
        while dq and dq[0] <= i - K:
            dq.pop_front()
        while dq and a[dq[-1]] <= a[i]:
            dq.pop_back()
        dq.append(i)
        if i >= K - 1:
            result.append(a[dq[0]])
    return result

구현

// Sliding window maximum, O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k; cin >> n >> k;
  vector<int> a(n);
  for (auto& v : a) cin >> v;
  deque<int> dq;
  for (int i = 0; i < n; i++) {
      while (!dq.empty() && dq.front() <= i - k)
          dq.pop_front();
      while (!dq.empty() && a[dq.back()] <= a[i])
          dq.pop_back();
      dq.push_back(i);
      if (i >= k - 1)
          cout << a[dq.front()] << ' ';
  }
}

from collections import deque
import sys
input = sys.stdin.readline
​
n, k = map(int, input().split())
a = list(map(int, input().split()))
dq = deque()
out = []
for i, v in enumerate(a):
  while dq and dq[0] <= i - k:
      dq.popleft()
  while dq and a[dq[-1]] <= v:
      dq.pop()
  dq.append(i)
  if i >= k - 1:
      out.append(str(a[dq[0]]))
sys.stdout.write(' '.join(out))

8 3
2 5 4 1 8 3 7 6

5 5 8 8 8 7

6 3
9 8 7 6 5 4

9 8 7 6 5

DP 최적화 예시

dp[i] = max(dp[i-1], max_{j in [i-K, i-1]} (dp[j] + a[i])) 형태에서, 덱에 dp[j] 를 단조 감소로 유지하며 O(N).

// dp[i] = max(dp[i-1], max_j (dp[j] + penalty) for j in [i-K, i-1])
// Deque trick O(N) instead of O(NK)
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k; cin >> n >> k;
  vector<long long> a(n), dp(n);
  for (auto& v : a) cin >> v;
  deque<int> dq;
  for (int i = 0; i < n; i++) {
      while (!dq.empty() && dq.front() < i - k)
          dq.pop_front();
      if (i == 0) dp[i] = a[i];
      else dp[i] = max(dp[i-1], (dq.empty() ? a[i] : dp[dq.front()] + a[i]));
      while (!dq.empty() && dp[dq.back()] <= dp[i])
          dq.pop_back();
      dq.push_back(i);
  }
  cout << dp[n-1] << '\n';
}

5 2
-1 -2 3 -4 5

5

복잡도

변형 / 활용

함정

1. 부호 방향 실수

최댓값을 구할 때는 a[dq.back()] <= a[i] 로 작거나 같은 값 제거. 최솟값은 >=. 방향 하나 틀리면 덱이 비어 있거나 결과가 틀린다.

2. 인덱스 vs 값 헷갈림

덱에는 인덱스를 저장해야 한다 (윈도우 이탈 판단에 필요). 값을 저장하면 pop_front 조건을 검사할 수 없다.

3. K 가 1 또는 N 일 때

K=1 이면 항상 a[i] 자체, K=N 이면 최댓값 하나만. 특수 케이스 처리가 필요 없지만 시간 복잡도는 그대로 O(N).

4. DP 에서 cost 분리 불가

cost(j, i) 가 A[j] + B[i] 로 분리되지 않으면 (예: cost = (x_i - x_j)^2) deque trick 적용 불가. 그 경우 Convex Hull Trick 또는 분할정복 DP 최적화 고려.

BOJ 연습 문제

참고

• Convex Hull Trick
• 분할정복 DP 최적화
• Slope Trick
• 크누스 최적화