monotone queue

Introduction

monotone queue 란 deque 의 상태를 증가하거나 감소하도록 유지시켜 수열의 특정 구간에서 최대 또는 최소를 찾는 기법이다.

 

다음의 문제를 보자.

http://boj.kr/11003

 

우리는 길이가 L 인 연속한 모든 구간들에 대해서 최솟값을 찾아줘야 한다. 물론 가장 naive한 방법으로는 세그먼트 트리를 이용한 방법이 있겠지만, monotone queue 테크닉을 사용하면 O(n)이라는 세그보다 (O(n log n)) 훨씬 빠른 속도로 문제를 풀 수 있다.

 

최솟값을 구하는 경우

i와 j는 i < j를 만족하고, 최솟값을 구하려는 하나의 구간에 속한다고 하자.

우리는 뒤로 진행해가며 각 구간의 최솟값을 구할려고 한다.

그렇기 때문에 i < j 이고 arr[i] > arr[j] 이라면 arr[i] 는 다시는 고려할 필요가 없다는것을 알 수 있다.

(arr[i]가 arr[j]보다 크고, arr[j]보다 먼저 사라지기 때문에 고려할 이유가 없다.)

 

이와 비슷하게 arr[i] = arr[j] 인 경우에도 arr[i]가 먼저 사라지므로 고려할 필요가 없다는것을 알 수 있다.

 

정리하자면 한 구간에서 i < j 이고 arr[i] >= arr[j] 이면 arr[i]의 값은 버려도 된다.

이를 통해 우리가 보고있는 구간에서 최솟값의 후보들을 index순으로 나열하면 값이 계속 증가하는 형태라는 것을 알 수 있다.

 

최솟값을 구하는 경우 - 알고리즘

우리가 보는 구간이 s ~ e 에서 s+1 ~ e+1 로 넘아가는 경우 어떤 일이 일어나는지 보자.

먼저 deque은 s ~ e 의 구간을 보았을 테고, 값이 증가하는 형태로 저장되어 있을 것 이다.

 

1. deque의 front에서 보면서 index가 s+1 ~ e+1보다 작은 값들을 pop해준다.

2. arr[e+1]을 deque에 넣어도 값이 계속 증가해야 함으로, deque의 back에서 보면서 값이 arr[e+1]보다 큰 값들은 pop한다

3. arr[e+1]의 값을 deque의 back에 push한다.

 

추가로 deque을 사용할때 값 하나로 관리하기보단 index, arr[index] 쌍으로 관리해야된다.

 

최댓값을 구하는 경우

최솟값을 구하는 경우와 크게 다르지 않다. 최솟값을 구하는 경우를 유도한것과 비슷한 방법으로 유도해 보면, 이번에는 값들을 감소하는 형태로 관리해야 된다는 것을 알 수 있다.

 

풀어보면 좋은 문제들

 

http://boj.kr/11003

monotone queue의 구현을 연습해볼수 있는 기본 문제이다.

 

http://boj.kr/3988

기본 문제를 조금 응용한 버전이라 어렵지 않게 풀 수 있다.