모노톤 스택 / 큐 / 덱

monotone 이라고 한다면 증가하고 있거나 감소하는 등의 (mono- ) 일정한 경향을 보임을 뜻한다.

그러한 형태를 띠는 스택, 큐, 덱인 것이다.

 

모노톤이라고 해서 한 방향을 띠긴 하지만, 모든 데이터를 담는 것은 아니다. 필요가 없어진 데이터는 버릴 수 있어야 하고, 필요가 없는 데이터는 기록조차 하지 않는다. 하지만 보통 이 방법을 통해 시간 복잡도를 O(N)으로 줄일 수 있어서 매우 강력하다고 생각한다.

 

다양한 활용처가 있겠지만, 이 포스트에서는 특정 범위내의 최대 / 최소를 구하는 방법에 대해 알아보고자 한다.

---

보통 최소값, 최대값 등을 구하기 위해 정렬을 한다. 정렬에도 다양한 방법이 있다.

하지만 정렬은 모든 데이터가 주어졌을 때 사용 가능하다. 더 이상 생성, 수정, 삭제 등의 연산이 없을 때 가능하다.

 

그래서 생성, 수정, 삭제 등의 연산이 발생한 후에 최대/최소를 어떻게 구할 것인지에 대한 문제가 남는다.

생성, 삭제 후의 최대/최소는 우선순위 큐를 구현하여 해결할 수 있다. 생성시 우선순위 큐에 계속 담아주면 된다.

삭제는? 담아줄 때 인덱스를 같이 담아서 삭제된 인덱스인지 확인해줄 수 있다. (요구사항이 무엇인지에 따라 물론 구현이 달라질 수 있다.)

 

기존 값이 수정된다면? 세그먼트 트리 등을 구성해서 해결할 수도 있겠다. 세그먼트 트리 포스팅도 올릴 마음만 먹은게 도대체 언제적인지...

 

그렇다면 특정 범위내에서의 최대 최소는 어떻게 찾을 것인가. 바로 이 모노톤 스택 / 덱 등을 활용하여 구할 수 있다.

• 문제에서 요구하는 범위를 벗어날 경우 과감히 스택 / 덱에서 버린다. 
• 정렬된 상태 유지를 위해 모노톤과 맞는 경우 값을 담는다.
• 모노톤 유지가 안된다면 모노톤이 될때까지 버린다. 
• 문제의 요구사항에 맞추어 모노톤 자료구조에 담을 때 처리를 하거나, 버릴 때 처리를 한다.

모노톤일 경우에만 처리가 필요한 범위가 만들어질 때 사용할 수 있다. O(1)로 계속 원소를 버려주면서 필요한 범위만 탐색하는 것이다.

이렇게 하면 자료구조에 데이터를 담을 때 O(1), 버릴 때 O(N) 을 한다. 그리고 그 자료구조는 항상 문제에서 원하는 범위를 유지하고 있다. 최대 최소는 가장 앞이나 뒤의 값만 O(1)을 들여서 읽으면 되는 것이다.

물론, 실제 구현시 쉽진 않겠지만, 이 방법은 매우 강력하며 반드시 숙지해야한다. 우선순위 큐보다도 빠르기 때문이다.

 

---

아래의 예제들을 통해 어떻게 쓰이는 지 이해할 수 있다.

백준 3015 오아시스 재결합

백준 3015 오아시스 재결합

백준 1725 히스토그램

백준 1725 히스토그램, 2104 부분배열 고르기

백준 11003 최솟값 찾기

백준 11003 최솟값 찾기