Monotone Queue Technique

이 글에서는 Monotone Queue Technique(모노톤 큐 테크닉) 에 대해서 가볍게 다뤄보려고 한다. DP에서 사용하는 Monotone Queue Optimization에 대해서 알고 싶다면 이 글을 참고하자. 

What is Monotone Queue?

Monotone Queue는 Monotone 과 Queue의 합성어이다. 즉 큐는 큐인데 단조로운 Queue라는 것이다. 즉, 어떠한 알고리즘을 토대로 큐를 단조롭게 관리하는 것이다. 당연히 큐를 단조롭게 관리함으로써 무엇인가를 얻을 수 있을 것이다. 

Problem 

예시 문제로 BOJ 11003 최솟값 찾기를 가지고 왔다. 전체 n개의 숫자내에 속한 임의의 크기 k인 구간에 대해서 최솟값을 구하는 문제이다. Naive 하게 풀면 $O(NK)$, 세그먼트 트리를 이용하면 $O(KlgN)$에 문제를 해결할 수 있지만, 이 문제에서는 $O(N)$에 푸는 것을 목표로 하고 있다.

How To Solve?

일단 $O(N)$에 구하기 위해서 하나 생각을 해보자. 순서를 중구난방이 아니라 순서대로 구할 것이다. 즉, $A_1...A_k$ 에서의 최솟값, $A_2...A_{k+1}$ 에서의 최솟값, $A_3...A_{k+2}$ 에서의 최솟값...  이런식으로 구해나가려고 한다.

일단 그 전에 관점을 바꿔서 생각해보자. 어떤 구간에 어떤 값이 포함되어져 있는 것이 아니라 어떤 값이 여러개의 구간에 영향력을 미치는 것이다. 즉 3번째 숫자는 위에서 언급한 3개의 구간에 영향력을 미치는 것이라고 바꿔서 생각하자. 

queue의 자료형은 pair로 <값,위치> 를 관리한다. 이때 큐 내에서 관리하는 pair의 "값"들은 증가하는 형태이다. 생각을 해보자. 값을 앞에서부터 순서대로 큐에 넣고 빼면서 관리를 할 것인데, 더 앞에 있고 더 큰 값은 영향력도 더 빨리 끝나고 최솟값으로 더 좋지도 않다. 따라서 아래와 같은 일련의 과정으로 모노톤 큐에 값들을 넣고 빼게 된다. 

1. 모노톤 큐의 맨 앞부분을 보면서 현재 위치까지 영향력을 줄 수 없는 모든 원소들을 앞에서 제거한다. (pop_front)

2. 모노톤 큐의 뒷 부분을 보면서 현재 넣고자 하는 값보다 모노톤 큐의 맨 뒤에 있는 원소가 크면 제거한다. 

3. 더 이상 맨 뒤에 있는 원소가 현재 넣고자 하는 값보다 크지 않거나, 큐가 빌 때까지 2번의 과정을 반복한다.

4. 현재 위치의 값을 넣는다.

5. 큐는 단조 증가하는 형태이기 때문에 구간내의 최솟값은 큐의 가장 앞에 있는 값이다.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
#define ff first
#define ss second
 
deque<pll> dq;
 
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    ll n,m,i,j;
    pll x;
    cin>>n>>m;
 
    for(i=1;i<=n;i++)
    {
        cin>>x.ff;
        x.ss=i;
        while(!dq.empty()&&x.ff<=dq.back().ff)
            dq.pop_back();
        dq.push_back(x);
        while(dq.front().ss<=i-m)
            dq.pop_front();
        cout<<dq.front().ff<<' ';
    }
}

추가로...

Monotone Queue Technique는 정말 중요하게 쓰이는 테크닉이다. 꼭 Monotone Queue가 아니더라도 Monotone 하게 관리하는 것은 꽤나 좋다. PS에서 쓸 이유가 없는 것을 쓰지 않고, 확인할 이유가 없는 것을 확인하는 것은 항상 좋은 일이다. 그리고 Monotone Queue는 그 점에 있어서 굉장히 유용하게 사용되어진다.
이번 글에는 그림을 넣지 않았지만, 혹시 이해가 안되시는 분이 있으면 댓글을 써주시면 그림을 추가해서 좀 더 자세히 설명을 해볼 예정이다.