테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 덱 (Deque) ======
  * Double-Ended QUEue의 약자
  * 덱이 맞는 발음이다. 디큐아님

===== Monotone deque =====
  * 참고: [[https://stonejjun.tistory.com/126]]
  * 덱 안의 원소들을 단조증가하는 순서대로 유지함으로써 문제를 푸는 테크닉. 
    * 새 원소를 덱 뒤에 추가시킬때, 덱 맨 뒤의 원소가 추가할 원소보다 작은 값이 될때까지 마지막 원소를 삭제한 뒤에, 새 원소를 추가한다. 사실 여기까지는 [[ps:스택#Monotone stack]]과 다를 바 없지만, 덱을 이용하면 이 상태에서 앞에서도 값을 제거할수 있다.
  * 이것을 활용하는 대표적인 작업은 [[ps:투 포인터]]나 슬라이딩 윈도우 방식으로 부분구간을 훑을때, 부분구간의 최솟값을 O(1)에 찾을수 있도록 유지해주는 것이다. 이런식으로 부분구간을 갱신하면, 덱 안에는 원소들은 인덱스 순서대로 추가되어서 저장되었을것이기 때문에, 인덱스 순서대로 삭제하는 것도 덱의 맨 앞에서부터 삭제해주면 된다. 덱은 항상 단조증가 상태로 유지되고, 최솟값은 덱의 맨 앞 원소가 된다.
    * 이것은 전체 크기 n인 배열에서, 크기 m짜리의 모든 부분구간에 대해서 최솟값을 찾는데에 O(n)이 걸린다. [[ps:우선순위큐]]를 써서 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는 상수시간이라고 가정하면.)
  * 관련 문제
    * [[ps:problems:boj:11003]] - 슬라이딩 윈도우 + monotone deque 를 쓰는 기본적인 문제
    * [[ps:problems:boj:15459]] - 투포인터 + monotone deque
    * [[ps:problems:boj:15678]] - monotone deque 를 DP를 푸는데 활용하는 전형적인 문제

==== 구현 ====
  * 이 테크닉을 설명하는 대부분의 블로그들 ([[https://stonejjun.tistory.com/126]], [[https://m.blog.naver.com/kks227/221386454504]], [[https://goldenriver42.tistory.com/135]])은 deque에 (원소값, 인덱스)의 페어를 넣어서, 뒤에서 지우는 것은 원소값을 기준으로, 앞에서 지우는 것은 인덱스를 기준으로 지우는 방식으로 소개한다.
    * 코드로 옮기면 이런 식이다
      * <dkpr py>
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])
</dkpr>

  * 그러나!! 굳이 페어를 저장하는 식으로 구현할 필요가 없다. 그냥 값만 저장해도 값 기준으로 지우는 것이 가능하다. 덱에 원소를 추가할때 기존의 마지막 원소를 제거할지 여부를 ≤이 아니라 < 로 체크하면 덱의 원소가 strictly increasing 하지 않고 non-decreasing 하게 된다 (중복이 허용된다는 소리). 그렇게 만들게 되면, j번째 인덱스 이하의 원소를 지우기 위하는 것을, 그냥 덱의 맨 앞의 원소가 A[j]와 같은지만 비교해서 지워주는 것으로 처리할수 있다.
    * 코드로 옮기면 이런 식이다
      * <dkpr py>
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])
</dkpr>
  * 위 코드를 좀더 효율적으로 바꿔쓰면 이런식이 된다. 이 방식을 표준 템플릿으로 사용하자.
    * <dkpr py>
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])
</dkpr>
    * 원소를 추가하기만 하는 L이전까지의 범위와, 추가와 삭제를 같이 하는 L이후의 범위를 다른 루프로 나눠서 처리하면 조금 더 속도를 올릴수는 있지만, 시간 단축이 그렇게 큰것도 아니고 코드가 길어지는게 더 별로여서 그 방식은 패스.
  * 이 테크닉을 이용해서 $ dp[i] = f(i, min_{i-K<j<i}(dp[j])) $ 형태의 DP를 푸는 문제는 이런식으로 코딩하면 된다
    * <dkpr py>
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()
</dkpr>