코딩 테스트 이론 - 단조 스택(Monotonic Stack)

단조 스택(Monotonic Stack)

 

**Monotonic Stack(단조 스택)**은 스택 자료구조를 활용하여 특정 조건을 만족하는 값을 효율적으로 찾는 알고리즘 기법입니다. 주로 배열이나 리스트에서 다음 큰 값(Next Greater Element), 다음 작은 값(Next Smaller Element) 등을 찾는 문제에서 사용됩니다.

---

Monotonic의 의미

• "Monotonic"은 단조라는 뜻으로, 값이 항상 증가하거나 감소하는 특성을 가집니다.
• Monotonic Stack에서는 스택 안에 들어 있는 값들이 다음 두 가지 조건 중 하나를 만족하도록 유지합니다:
  1. 단조 증가 스택 (Monotonic Increasing Stack):
     • 스택에 값이 쌓일수록 값이 커지거나 같음.
     • 즉, 스택의 위쪽에 있는 값이 아래쪽 값보다 항상 크거나 같음.
  2. 단조 감소 스택 (Monotonic Decreasing Stack):
     • 스택에 값이 쌓일수록 값이 작아지거나 같음.
     • 즉, 스택의 위쪽에 있는 값이 아래쪽 값보다 항상 작거나 같음.

---

Monotonic Stack의 특징

1. 효율성:
   • 배열에서 특정 값을 찾는 문제를 단조 스택으로 풀면, 시간 복잡도가 O(n)으로 최적화됩니다.
   • 배열을 한 번 순회하면서 값을 스택에 추가하거나 제거하기 때문입니다.
2. 스택 유지:
   • 새로운 값을 처리할 때, 스택의 "단조 조건"이 깨지는 값을 제거하고 새로운 값을 넣습니다.
3. 사용 사례:
   • 다음 큰 값(Next Greater Element) 찾기
   • 다음 작은 값(Next Smaller Element) 찾기
   • 히스토그램의 최대 면적(Maximum Rectangle in Histogram)
   • 주식 가격 문제(Stock Span Problem)
   • Sliding Window Maximum 등

 

Monotonic Stack의 장점

1. 효율적인 탐색:
   • 기존 방식으로 각 값의 "다음 큰 값"을 찾으려면 O(n^2)이 필요하지만,
   • Monotonic Stack은 한 번의 순회, O(n)로 해결 가능 .
2. 직관적 설계:
   • 문제를 단순히 "단조 조건"으로 정리하여 풀이 과정을 명확히 이해하고 구현할 수 있음.

---

정리

Monotonic Stack은 스택을 활용하여 배열의 특정 값들을 효율적으로 탐색하는 기법입니다. 배열에서 다음 큰 값, 다음 작은 값과 같은 문제에서 특히 유용하며, O(n)의 시간 복잡도를 보장합니다. 단조 증가나 단조 감소 조건을 유지하면서 값을 추가 및 제거하는 방식이 핵심입니다.

 

참고 자료

 

https://hphhbva.tistory.com/91

Monotonic Stack에 대하여

 

https://youtu.be/Dq_ObZwTY_Q?si=5I9IXawluSOtkmz5