덱 (Deque)

Double-Ended QUEue의 약자
덱이 맞는 발음이다. 디큐아님

Monotone deque

참고: https://stonejjun.tistory.com/126
덱 안의 원소들을 단조증가하는 순서대로 유지함으로써 문제를 푸는 테크닉.
- 새 원소를 덱 뒤에 추가시킬때, 덱 맨 뒤의 원소가 추가할 원소보다 작은 값이 될때까지 마지막 원소를 삭제한 뒤에, 새 원소를 추가한다. 사실 여기까지는 Monotone stack과 다를 바 없지만, 덱을 이용하면 이 상태에서 앞에서도 값을 제거할수 있다.
이것을 활용하는 대표적인 작업은 투 포인터나 슬라이딩 윈도우 방식으로 부분구간을 훑을때, 부분구간의 최솟값을 O(1)에 찾을수 있도록 유지해주는 것이다. 이런식으로 부분구간을 갱신하면, 덱 안에는 원소들은 인덱스 순서대로 추가되어서 저장되었을것이기 때문에, 인덱스 순서대로 삭제하는 것도 덱의 맨 앞에서부터 삭제해주면 된다. 덱은 항상 단조증가 상태로 유지되고, 최솟값은 덱의 맨 앞 원소가 된다.
- 이것은 전체 크기 n인 배열에서, 크기 m짜리의 모든 부분구간에 대해서 최솟값을 찾는데에 O(n)이 걸린다. 우선순위 큐 (Priority Queue)를 써서 O(nlogm)에 찾는 것보다 당연히 효율적이고 코드도 별로 복잡하지 않다.
- 만약, 최솟값을 찾아야 하는 구간의 크기가 항상 고정된 경우라면 https://kim1109123.tistory.com/83 의 방법을 통해서도 O(n)에 구할수 있기는 하다.
이렇게 슬라이딩 윈도우에서 부분구간의 최솟값을 효율적으로 유지할수 있다면, 특정한 형태의 DP를 효율적으로 풀수 있다. 점화식의 형태가 i번째 DP값을, 이전 K개의 DP값의 최솟값으로부터 구해야 하는 방식 (즉, $ dp[i] = f(min_{i-K<j<i}(dp[j])) $ 와 같은형태) 라면 이 방식으로 O(nK)가 아닌 O(n)으로 구할수 있다 (f는 상수시간이라고 가정하면.)
관련 문제
- 최솟값 찾기 - 슬라이딩 윈도우 + monotone deque 를 쓰는 기본적인 문제
- Haybale Feast - 투포인터 + monotone deque
- 연세워터파크 - monotone deque 를 DP를 푸는데 활용하는 전형적인 문제

구현

이 테크닉을 설명하는 대부분의 블로그들 (https://stonejjun.tistory.com/126, https://m.blog.naver.com/kks227/221386454504, https://goldenriver42.tistory.com/135)은 deque에 (원소값, 인덱스)의 페어를 넣어서, 뒤에서 지우는 것은 원소값을 기준으로, 앞에서 지우는 것은 인덱스를 기준으로 지우는 방식으로 소개한다.
- 코드로 옮기면 이런 식이다
  - ```
  deq = collections.deque()
  for i, a_i in enumerate(A):
      while deq[0][1] <= i - L:
          deq.popleft()
      while deq and deq[-1][0] >= a_i:
          deq.pop()
      deq.append((a_i, i))
      
      min_val = deq[0][0]  # min_val == min(A[i-L+1], ... , A[i])
```

그러나!! 굳이 페어를 저장하는 식으로 구현할 필요가 없다. 그냥 값만 저장해도 값 기준으로 지우는 것이 가능하다. 덱에 원소를 추가할때 기존의 마지막 원소를 제거할지 여부를 ≤이 아니라 < 로 체크하면 덱의 원소가 strictly increasing 하지 않고 non-decreasing 하게 된다 (중복이 허용된다는 소리). 그렇게 만들게 되면, j번째 인덱스 이하의 원소를 지우기 위하는 것을, 그냥 덱의 맨 앞의 원소가 A[j]와 같은지만 비교해서 지워주는 것으로 처리할수 있다.
- 코드로 옮기면 이런 식이다
  - ```
  deq = collections.deque()
  for i, a_i in enumerate(A):
      if i >= L and deq[0] == A[i - L]:
          deq.popleft()
      while deq and deq[-1] > a_i:
          deq.pop()
      deq.append(a_i)
      min_val = deq[0]  # min_val == min(A[i-L+1], ... , A[i])
```
위 코드를 좀더 효율적으로 바꿔쓰면 이런식이 된다. 이 방식을 표준 템플릿으로 사용하자.
- ```
deq = collections.deque()
for left, right in zip(itertools.chain([None] * L, A), A):
    while deq and deq[-1] > right:
        deq.pop()
    deq.append(right)
    if deq[0] == left:
        deq.popleft()
    min_val = deq[0]  # min_val == min(A[i-L+1], ... , A[i])
```
- 원소를 추가하기만 하는 L이전까지의 범위와, 추가와 삭제를 같이 하는 L이후의 범위를 다른 루프로 나눠서 처리하면 조금 더 속도를 올릴수는 있지만, 시간 단축이 그렇게 큰것도 아니고 코드가 길어지는게 더 별로여서 그 방식은 패스.

이 테크닉을 이용해서 $ dp[i] = f(i, min_{i-K<j<i}(dp[j])) $ 형태의 DP를 푸는 문제는 이런식으로 코딩하면 된다

deq = collections.deque([INF])
dp = [None] * N
for i in range(N):
    min_val = deq[0]
    dp[i] = f(i, min_val)
    while deq and deq[-1] > dp[i]:
        deq.pop()
    deq.append(dp[i])
    if deq[0] == dp[i - K]:
        deq.popleft()

목차

덱 (Deque)

Monotone deque

구현