단조 스택1 Monotonic Stack에 대하여 알고리즘 문제를 풀다가 처음 마주하는 개념을 알게 되었다. 이름을 알게 된 김에 가볍게 내용을 정리해보았다. Monotonic Stack이란 : 스택 내의 요소들이 단조적으로(Monotonic) 증가/감소하는 스택을 말한다. 아래와 같은 특징을 갖는다고 한다. 한 번 pop된 요소는 다시는 재사용 되지 않는다. 요소를 스택에 추가할 때마나 단조성을 유지한다. → 이러한 특징 때문에 주로 다음/이전의 최소값/최대값(Next/Previous smaller/larger Problem)을 구하는 문제에서 잘 쓰인다. Monotonic Stack의 구현 Monotonic Stack의 구현에는 아래의 과정을 거친다. 아래는 감소하는(Decreasing) 스택을 구하는 과정이다. 기본적으로, 주어진 숫자 목록을 순회.. 2024. 4. 14. 이전 1 다음
