[자료구조] 모노토닉 큐 (Monotonic Queue)

사진: Unsplash 의 Hal Gatewood

 

알고리즘 공부를 하면서 새롭게 배운 자료구조가 생겼다.

모노토닉 큐(Monotonic Queue) 라고 부르는 녀석인데, 단조 덱(Monotonic Deque), 모노 덱 등 다양한 이름을 가졌다.

정확히는 '모노토닉 큐'가 정확한 표현인 것 같아서 제목은 이것으로 결정했다.

('큐'인데 '덱'을 쓴다.)

 

---

모노토닉 큐의 기본 개념

모노토닉 큐란, 덱(deque)을 이용해 내부 원소가 항상 단조 증가 혹은 단조 감소하도록 유지하는 자료구조이다.

덱의 원소들이 값 기준으로 정렬된 상태를 유지하면서도 시간 순서 또한 보장된다.

이는 슬라이딩 윈도우 문제를 해결할 때 최댓값 혹은 최솟값을 효율적으로 관리하기 위해 사용된다.

 

슬라이딩 윈도우에서의 모노토닉 큐

 

일반적으로 투 포인터를 활용한 슬라이딩 윈도우 문제에서는 start와 end 사이의 범위 k 내에서 최댓값을 구하려면 매 윈도우 범위마다 k개의 원소를 전부 확인해야 하므로 O(nk)의 시간 복잡도를 나타낸다.

 

심지어는 슬라이딩 윈도우는 '정렬 되어있는 배열' 에서 사용되어야 하므로, O(n log n)의 시간 복잡도가 소요되는 정렬이 선행되어야 한다.

 

하지만 모노토닉 큐를 활용하면 이런 불필요한 비교를 피하며 O(n)의 시간복잡도로 정렬과 슬라이딩 윈도우를 동시에 구현할 수 있다.

 

* 단조(Monotonic)

증가하거나 감소하는 방향성이 한쪽으로만 일정한 것

• 단조 증가(Monotone increasing) - 앞에서 뒤로 갈수록 값이 같거나 큰 형태
• 단조 감소 (Monotone decreasing) - 앞에서 뒤로 갈수록 값이 같거나 작은 형태

그렇다면 왜 덱을 단조롭게 유지해야 하는걸까?

위에서 말했듯 모노토닉 큐를 이용하면 덱의 원소들이 값 기준으로 정렬된 상태에 더불어서 시간 순서도 보장된다.

이를 이용해서 front에 항상 '최댓값' 혹은 '최솟값'을 남기기 위해서이다. 여기서 front에 남는 최댓값(최솟값)은 현재 구간에서 최댓값 후보 중 가장 오래된 것이 보장되므로 진짜 최댓값이 되기 때문이다.

 

모노토닉 큐는 다음과 같은 방식으로 단조를 유지한다.

예를 들어, 배열 A에서 크기 k의 윈도우마다 최댓값을 구한다고 가정할 때,

한 칸 씩 윈도우를 옮길 때마다

1. 새로 들어오는 원소 A[i]보다 작은 값들은 최댓값 후보가 될 수 없으므로 덱의 back에서 제거한다.
2. A[i]를 덱의 back에 push 한다.
3. 윈도우 범위를 벗어난 가장 앞 원소가 있다면 덱의 front에서 제거한다.
4. 덱의 front의 원소는 현재 윈도우에서의 최댓값임이 보장된다.

덱의 원소로는 주로 인덱스와 값을 함께 저장하는 pair<T, T>를 활용한다.

(원본 배열을 저장해도 공간 복잡도가 허용한다면 인덱스만 저장해도 되지만)

 

아래 예시를 만들어왔다. 예시를 보면서 모노토닉 큐를 통해 구간의 최댓값을 구하는 방법을 알아보자.

dq의 조작은 C++을 기준으로 설명한다.

 

A = [1, 3, -1, -3, 5, 3, 6, 7] 배열이 있고, dq라는 이름의 덱을 사용한다.

윈도우 크기 k가 3이라고 가정하며 각 구간에서의 최댓값을 찾아보자.

배열의 인덱싱은 편리를 위해 1부터 시작한다.

figma로 이미지를 만들 때에 넣진 못했는데, 덱 dq의 최대 크기는 k와 동일한 3이다.

 

덱에 A[1] 원소를 인덱스와 함께 push 한다. 아직 구간이 형성이 되지 않았지만 현재 덱의 내부 상황에서 1은 최댓값이다.

이제 범위를 윈도우의 범위 내에서 A의 원소를 계속해서 push 하려고 해보자.

 

 

A[2]의 3은 dq.front().second인 1보다 크다. 따라서 더 이상 최댓값이 될 수 없으므로 dq에서 pop하여 제거한다.

그리고 (2,3)을 dq.push_back() 한다.

 

A[3]의 -1은 dq.front().second의 3보다 작으므로 (3, -1)을 dq.push_back() 한다.

현재 윈도우 구간 내의 최댓값은 3이다.

이제 윈도우를 한 칸 밀어보자.

 

(4, -3)을 넣어도 덱은 여전히 단조하게 감소하는 형태를 띄며 dq.front()는 최댓값임이 보장되고 있다.

또 윈도우를 한 칸 밀어 새 요소를 넣으려고 해보자.

 

윈도우를 밀면 현재 구간의 범위 밖이므로 이전 구간에서의 최댓값이었던 dq.front()를 제거해야한다.

dq.pop_front()로 제거한다.

그리고 다음 요소 A[5]를 넣기 위해 비교하고자 하면...

 

(3, -1)과 (4, -3)의 값 -1, -3은 5보다 작다. 그러므로 새로 삽입된 요소 A[5]의 (5, 5)가 덱의 맨 앞에 올 수 있도록 두 요소를 제거해주어야 한다.

동시에 윈도우 내 최댓값은 5가 되며, 덱 dq에는 (5, 5)만이 남아있게 된다.

 

윈도우가 다음 구간으로 넘어가도 덱에는 push_back() 연산만 발생하고 단조 감소를 유지하고 있으며 여전히 윈도우 내 최댓값은 5이다.

 

다음 구간으로 넘어가서 A[7]인 6을 넣어보려고 하면 앞서 (5, 5)를 넣을 때와 마찬가지로 6보다 작은 5, 3 두 요소를 제거해야 한다.

dq.front()는 구간의 최댓값인 6으로 바뀐다.

 

마지막 구간에서 A[8]을 덱 dq에 넣으려고 하면 당연히 6이 7보다 작기 때문에 dq.pop_front() 연산을 통해 덱의 front를 최댓값으로 유지해준다.

 

이렇게 해서 각 구간의 최댓값을 구할 수 있다.

덱에 각 원소는 한 번 들어오고 나가기 때문에 O(n)에 모든 윈도우의 최댓값을 구하는 것이 가능하다.

 

모노토닉 큐의 활용

 

그렇다면 정렬과 슬라이딩 윈도우가 한 번에 가능한 이 기특한 녀석을 어디에 활용할 수 있을까?

슬라이딩 윈도우 구간 내의 최댓값, 최솟값을 구하는 문제인데 정렬과 슬라이딩 윈도우를 차례로 수행할 때 시간 초과가 나는 문제들이나

DP 최적화에도 사용될 수 있다.

O(n log k)의 시간복잡도를 갖는 우선순위 큐 (Priority Queue)보다도 빠른 시간복잡도를 갖기에 우선순위 큐가 사용될 곳에 사용해도 되지 않을까 싶은 생각도 든다.

 

---

 

이렇게 모노토닉 큐에 대한 기본 골자를 간단히 정리해보았다.

백준 온라인 저지의 11003번, 15678번 문제를 풀며 학습해보았고, 굉장히 신선하고 재미있는 자료구조를 새로 알게 되었다.

모노토닉 큐 덕분에 BOJ를 풀며 처음으로 플래티넘 티어의 문제를 건들여보아서, 내게는 감사한 마음도 큰 자료구조다.

앞서 말한 두 문제에 대한 풀이도 금방 포스팅하겠다!