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는 상수시간이라고 가정하면.)
- 관련 문제
- 최솟값 찾기 - 슬라이딩 윈도우 + 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()
ps/덱.txt · 마지막으로 수정됨: 2024/05/13 14:32 저자 teferi
토론