Monotone stack
설명 모노톤 스택(Monotonic Stack)은 주어진 배열에서 각 원소에 대해 다음에 올 원소를 찾거나, 또는 이전에 올 원소를 찾는 데에 사용되는 자료 구조이다. 주로 "더 큰 원소를 찾아라" 또는 "더 작은 원소를 찾아라"와 같은 상황에서 유용하게 활용된다. 모노톤 스택의 두 가지 유형: 단조 증가 스택 (Increasing Monotonic Stack): 스택에 원소를 추가할 때, 스택의 맨 위에 있는 원소보다 큰 값을 가진 원소만 추가한다. 이 스택은 "더 큰 원소를 찾아라"와 같은 상황에서 사용된다. 단조 감소 스택 (Decreasing Monotonic Stack): 스택에 원소를 추가할 때, 스택의 맨 위에 있는 원소보다 작은 값을 가진 원소만 추가한다. 이 스택은 "더 작은 원소를 찾아..
Programming/알고리즘
2024. 1. 16. 21:48