Monotone Queue Technique (Sliding window, DP 최적화)

특징

- sliding window처럼 일정 범위 내의 '유효한' 값만 저장 (유효하지 않으면 pop해버림)

- heap 처럼 맨 앞에 min/max 값을 저장.

(엄밀히 말하자면, deque내의 원소들을 monotonic increasing/decreasing 상태로 유지)

☞ Sliding window min/max 구하기, DP 최적화 등에 쓰인다

 

 

sliding window를 움직이면서 매번 max를 구하는 문제를 생각해보자.

max값만 tracking하면, window가 기존의 max값을 지나치는 경우 새 max값 업데이트를 어떻게 할 것인가?

 

1 [5 4 -1] 3 0 → max 5

1 5 [4 -1 3] 0 → max 4

1 5 4 [-1 3 -5] → max 3

 

맨 처음에 max 5였다가, window가 이동하면서 max가 4로 바뀌었다.

이 경우, 2nd max 4가 새로운 max가 된다.

그럼 앞으로도 window를 움직이다가 max가 바깥으로 튕겨나가면 max자리에 2nd max를 끼워넣기만 하면 되는게 아닌가 싶다.

근데 그러면 2nd max의 자리가 비게 된다. 이건 3rd max로 채워줘야 하고, 3rd max의 빈자리는 4th max로, ....

즉 이 방식으로는 max, 2nd max, ..., kth max 까지 등장하는 위치 index와 함께 관리해줘야 한다.

그냥 완전탐색과 다를바가 없지 않은가?

 

 

이걸 편하게 deque을 이용해서 처리할 수 있다.

monotone deque : 이름에서 나오다시피, deque가 담고 있는 원소들이 단조 증가/감소하도록 관리한다.

 

예를 들어, front 원소가 max값인 decreasing monotone queue를 구현한다고 하자.

새로 push_back 하기 전에, 새로 넣을 원소의 값보다 deque.back()이 작으면 pop_back()한다.

더 이상 pop_back()할게 없을 때 새 원소를 넣으면 원소들이 monotonic decreasing하게 된다.

 

또, sliding window 범위 바깥으로 벗어난 원소는 제거해줘야 한다. deque에 원소를 넣을 때 {값, 위치 idx} 를 함께 넣어서 window내의 원소인지 체크한다.front()원소가 범위 내인지 체크하고 아니라면 pop_front() 

// decreasing monotone queue example (max at front)
while (head < nums.size()) {
  while (!q.empty() && q.back().first < nums[head]) q.pop_back(); // push new
  q.emplace_back(nums[head], head);

  while (!q.empty() && q.front().second < tail) q.pop_front(); // remove outdated
  head++; tail++;
}

 

기본 개념이 이렇고, 여러 가지 문제에서 변형되어 활용가능하다.

---

https://leetcode.com/problems/jump-game-vi/

이 문제를 통해 처음 접한 개념.

raw DP로는 O(N^2) 에서 벗어날 수 없는 것 같았는데, PQ 혹은 deque을 이용해서 최적화 하더라

 

이 문제 Discussion 읽어보면 관련된 좋은 설명 많다.

https://leetcode.com/problems/jump-game-vi/discuss/978497/Python-DP-%2B-Sliding-Window-Maximum-problem-combined

[Python] DP + Sliding Window Maximum problem combined - LeetCode Discuss

 

개념 설명 + 이걸로 풀 수 있는 문제들 소개 (꽤 어려움)

https://1e9.medium.com/monotonic-queue-notes-980a019d5793

Monotonic Queue Algorithms

 

다른 개념 설명 (아래 부분 깔끔함)

https://stonejjun.tistory.com/126

Monotone Queue Technique

Monotone Queue Technique.mhtml

0.38MB

 

---

관련 문제

BOJ 196 11003 최솟값 찾기

LeetCode 24 M-1696 Jump Game VI

LeetCode H-239 Sliding Window Maximum