[Algorithm] Monotonic Stack

1. Monotonic Stack

단조 스택(Monotic Stack)은 알고리즘 문제 해결에 사용되는 특수 구조이며, 각 element들을 오름, 내림 차순으로 유지하는 알고리즘 기법이다. 일반적으로 배열에서 다음으로 크거나 작은 element를 찾는 등의 문제를 효율적으로 해결하는데  사용된다. 

Monotonic Stack

기존의 스택과 달리 단조 스택의 조건은 스택의 내부 element가 들어오는 element에 따라 증가, 감소하는 배열이 되도록 순서를 구성해주어야 한다. 

2. 유형

단조 스택의 유형은 두가지로 분류될 수 있다. 

• 오름차순 단조 스택 (Monotic Increasing Stack)

스택에 추가되는 현재 들어오려는 element는 스택에 저장된 element들보다 크거나 같아야 한다. 새 element의 크기가 작으면 새 element보다 작거나 같은 element를 찾을 때까지 혹은 스택이 비었을 때까지 top element 부터 제거해주어야 한다.

 

간단하게 예시를 들어서 살펴보자

배열에는 1, 7, 9, 5가 저장되어 있고 이에 따른 오름차순 단조 스택을 이용한다.

배열이 비어있으므로, 현재 element가 스택에 들어가게 된다.

두번째 element에서는 top보다 크기가 크므로 따로 pop하지 않고 7이 push되어 스택의 top이 바뀌게 된다.

세 번째 element 또한 앞서 저장된 스택의 element보다 더 크므로, pop이 되지 않고 9가 push된다.

 

마지막 element는 9보다 작으므로 9는 pop된다.

7 또한 마지막 element보다 더 크므로 pop된다. 7이 빠진 후 남게되는 1은 5보다 작으므로 5가 push되어 아래의 그림처럼 최종적으로 스택이 완성되게 된다. 

마지막 요소를 거친 후의 스택 모습

시간 복잡도 : O(N) 

Input Array의 각 element는 스택에서 한번만 푸쉬되고 팝업되므로 O(N)을 따르게 된다.

임시 공간(Auxiliary Space) : O(N)

• 내림차순 단조 스택 (Monotic Decreasing Stack)

오름차순과 다르게 스택에 추가되는 현재 들어오려는 element는 스택에 저장된 element들보다 작거나 같아야 한다. 새 element의 크기가 크면 새 element보다 크거나 같은 element를 찾을 때까지 혹은 스택이 비었을 때까지 top element 부터 제거해주어야 한다.

 

간단하게 예시를 들어서 살펴보자

배열에는 7, 5, 9, 4가 저장되어 있고 이에 따른 내림차순 단조 스택을 이용한다.

배열이 비어있으므로, 현재 element가 들어가게 된다.

두 번째 element에서는 top보다 크기가 작으므로 따로 pop하지 않고 5가 push되어 스택의 top이 바뀌게 된다.

현재 element인 9는 5보다 크므로 5는 pop된다. 

7 또한 5와 동일하게 9가 더 크므로 7은 pop된다. 

결국 스택은 비게 되므로 더이상 비교하지 않고 9가 push된다. 

마지막 요소를 거친 후의 스택 모습

마지막 element인 4는 9보다 작으므로 스택에 push된다.

최종적으로 스택에 남게되는 요소는 위와 같다. 

 

시간 복잡도와 임시 공간은 모두 오름차순과 동일하다. 

3. 장단점

배열에서 다음으로 크거나 작은 element들을 찾는데 효율적이며, 가장 가까운 작은 원소를 찾거나 히스토그램의 최대 면적을 계산하는 등 스택 응용 문제들을 해결하는데 유용하다. 또한, 시간 복잡도도 선형이므로 대규모 dataset을 처리하는데 효율적이다는 장점이 존재한다.

이에 반해 스택을 저장하기 위해 추가 공간이 필요하다는 불필요함이 존재하고, 초보자가 이해하고 구현하기에는 직관적이지 않다는 단점이 존재한다. 

4. 응용

백준에서 스택 응용 문제를 풀어보았다. 자세한 링크는 이곳을 참조하면 된다. 

---

참고 문헌

https://www.geeksforgeeks.org/introduction-to-monotonic-stack-2/

Introduction to Monotonic Stack - Data Structure and Algorithm Tutorials - GeeksforGeeks