사용자 도구

사이트 도구


ps:덱

덱 (Deque)

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

Monotone deque

  • 덱 안의 원소들을 단조증가하는 순서대로 유지함으로써 문제를 푸는 테크닉.
    • 새 원소를 덱 뒤에 추가시킬때, 덱 맨 뒤의 원소가 추가할 원소보다 작은 값이 될때까지 마지막 원소를 삭제한 뒤에, 새 원소를 추가한다. 사실 여기까지는 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는 상수시간이라고 가정하면.)
  • 관련 문제

구현

  • 이 테크닉을 설명하는 대부분의 블로그들 (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(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()

토론

댓글을 입력하세요:
L H K N B
 
ps/덱.txt · 마지막으로 수정됨: 2023/03/09 02:26 저자 teferi