내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
덱 (Deque)
ps:덱
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 덱 (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>
ps/덱.txt
· 마지막으로 수정됨: 2024/05/13 14:32 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로