단조 큐 (Monotone Queue)

개요

큐에 들어있는 어떠한 값들의 집합이 단조성을 보이면(monotonic) 그 큐는 단조 큐가 된다.

 

예를 들어 큐 안에 있는 수들을 수열로 봤을 때 단조증가한다면 단조 큐다.

 

용어는 단조 큐이지만 이를 활용하기 위해서 덱(deque)이 쓰인다.

단조 큐를 활용한 문제 풀기

백준 저지에서 11003번 문제를 보자.

 

수열을 순회하면서 특정 구간에 대해 최솟값을 찾을 것을 요구하고 있다.

 

어떤 구간에서 최솟값보다 큰 수들은 무시된다는 점에 주목해보자.

 

수열을 순회하면서 상대적으로 큰 수들을 적절히 배제하고 구간에 알맞은 최솟값을 남길 수 있다면 좋을 것이다.

 

여기서 단조 큐를 이용하면 $O(N)$으로 빠르게 답을 구할 수 있게 된다.

 

11003번 문제를 푸는 과정을 통해 단조 큐 사용법을 알아보자.

 

1. 수열을 순회하면서 항을 덱에 넣기 전에 덱에서 항보다 크거나 같은 값들을 뒤에서부터 모두 제거한다. 이렇게 되면 현재 항보다 큰 수들을 무시할 수 있게 된다.

 

2. 현재 항을 덱의 뒤에 넣는다.

 

3. 구간 조건에 만족하지 않는 수들을 덱의 앞에서부터 모두 제거한다.

 

4. 이러면 덱의 front가 해당 구간의 최솟값이 되고 큐에 있는 원소들은 단조성을 가지게 된다.

 

이렇게 단조 큐를 활용하면 필요 없는 값들을 쉽게 배제하고 사용해야 하는 값을 바로 취할 수 있어 단조 큐를 활용할 수 있는 문제에서 큰 이득을 얻을 수 있다.

 

소스 코드 - BOJ 11003

#include <bits/stdc++.h>
     
using namespace std;
using pii = pair<int, int>;
  
int n, l;
deque<pii> dq;
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n >> l;
 
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
 
        while (dq.size() && dq.back().first >= x)
            dq.pop_back();
        dq.push_back({x, i});
        while (dq.front().second <= i - l)
            dq.pop_front();
        
        cout << dq.front().first << ' ';
    }
}

단조 큐를 이용할 수 있는 문제

대표적으로 연세워터파크가 있다. dp테이블을 단조 큐에 관리해서 계산을 빠르게 할 수 있다.

 

그 밖에도 백준에서 덱을 이용한 다이나믹 프로그래밍, 단조 큐를 이용한 최적화 태그가 붙은 문제가 단조 큐를 이용하는 문제이다.

 

찾아서 풀어보자.