ps:스택
스택 (Stack)
- 몇가지 대표적인 활용은, 괄호쌍 매칭, infix order를 변환하기, Monotone stack 등이다.
Monotone Stack
- Monotonic stack 이라고 불리기도 한다.
- 스택 안에 원소들을 정렬된 순서로 유지하면서 문제를 해결하는 테크닉이다. 구체적인 설명은 https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/ 참고
- 기본적인 활용법은, All nearest smaller values 라고 불리우는 문제이다. 시퀀스 A의 모든 원소들 A[i]에 대해서 j<i이면서 A[j]<A[i] 인 가장 큰 j를 찾는 것이다. 여기서는 활용문제를 더 설명하기 쉽게하려고, nearest greater value로 바꾸겠다. NGV[i] 는 j<i이면서 A[j]>A[i]인 가장 큰 j 라고 하겠다 (값이 아니라 인덱스이다)
- i까지의 NGV를 모두 구했다면, NGV[i]의 NGV, 또 거기서의 NGV를 나열할수 있다. A[i], A[NGV[i]], A[NGV[NGV[i]]], … 은increasing sequence가 된다. (longest increasing sequence 가 되는 것은 아니다. 기준이 애초에 다르다)
- 기하학적으로 표현하면 의미가 쉬워진다. 문제에서도 이 형태로 주어지는 경우가 많다. 1차원 좌표위에 건물들이 늘어서 있고, i위치의 건물의 높이가 A[i]라고 주어졌을 때, NGV[i]는 i 건물의 옥상에서 왼쪽을 봤을때 처음으로 보이는 A보다 높은 건물의 위치이다. NGV를 따라가면서 만들었던 증가수열은, i건물에서 왼쪽을 봤을때 가려지지 않고 보이는 모든 건물들을 뜻한다.
- Monotone stack 기법을 통해서, A[i]가 추가될때마다 이러한 시퀀스를 계속 유지할 수 있다. 각 원소를 추가할때마다, 현재보다 큰 원소가 stack의 탑에 올때까지 pop을 해준 다음에 현재 원소를 push해주기만 하면 된다. n개의 원소를 처리하는 데에 amortized O(n)에 처리된다.
스택을 안쓰고 푸는 방법
- 이 문제는 스택 없이도 사실 가능하다. NGV만 잘 저장해두면 된다
- NGV[i]를 구하기 위해서는, A[i]를 A[i-1]과 먼저 비교해보고, 만약 A[i-1]이 더 작으면, A[NGV[i-1]], A[NGV[NGV[i-1]]], .. 와 비교해서 A[i]보다 큰값이 나오면 그 인덱스를 NGV[i]에 저장하면 된다. 사실 동작 원리는 monotone stack과 동일하다. 속도가 약간 빠르기는 하지만 작은 차이이고, 코드가 덜 깔끔해지기 때문에 일반적으로는 그냥 monotone stack을 쓰자.
관련 문제
ps/스택.txt · 마지막으로 수정됨: 2024/01/27 09:40 저자 teferi
토론