Monotonic Stack, Queue 활용
Monotonic 이란
단조로운 이라는 뜻으로 일정한 규칙을 가진 자료구조를 의미합니다. 대표적으로 Monotonic Stack과 Monotonic Queue가 있습니다.
Monotonic Stack
내림차순 혹은 오름차순으로 쌓을 수 있는 Stack 자료구조입니다. 스택에 넣은 데이터는 규칙을 유지하기 위해 데이터를 제거합니다(pop).
오름차순 Monotonic Stack은 스택을 오름차순 순으로 쌓으며 제일 아래해 항상 현 시점 가장 작은 원소 가 있음을 보장합니다.
nums = [2,3,4,1,5,-1]
stack = []
for idx, num in enumerate(nums):
while stack and stack[-1] > num:
stack.pop()
stack.append(num)
print(f"[현재 인덱스 : {idx}] 현재 가장 작은 element : {stack[0]}")
출력은 다음과 같이 가장 작은 element를 보장합니다.
[현재 인덱스 : 0] 현재 가장 작은 element : 2
[현재 인덱스 : 1] 현재 가장 작은 element : 2
[현재 인덱스 : 2] 현재 가장 작은 element : 2
[현재 인덱스 : 3] 현재 가장 작은 element : 1
[현재 인덱스 : 4] 현재 가장 작은 element : 1
[현재 인덱스 : 5] 현재 가장 작은 element : -1
가장 작은 원소값을 찾는 것이라면 아래처럼 최소값을 유지하면 되지 않을까요?
nums = [2,3,4,1,5,-1]
minval = float('inf')
for idx, num in enumerate(nums):
minval = min(minval, num)
print(f"[현재 인덱스 : {idx}] 현재 가장 작은 element : {minval}")
Monototic Stack은 현 시점 가장 작은 원소 뿐만 아니라 두 번째 세 번째로 작은 원소 값도 구할 수 있도록 저장합니다.
따라서 현 시점에서 제일 작은 원소만 고려해야할 사항 뿐만 아니라 n 번째 작은값을 구해야 할 때 활용할 수 있습니다.
Daily Temperatures
문제 링크
날 별 온도 값
temperatures가 주어질 때 각 temperature index 인i번째 온도가 몇 일만에 높아지는지 구한다.
해당 문제는 위에서 언급한 Monotonic Stack을 활용해 해결이 가능합니다. stack에는 내림차순 Monotonic Stack을 활용하여 온도의 index를 저장하고 현 시점 보다 큰 온도 값을 저장할 때 Stack에 저장되어 있는 이전 날짜 값을 빼서(pop) 현재 날짜와 차이를 계산하면 됩니다.
해당 문제는 i 번째 이후에 몇 일만에 높아지는지 구하라고 설명되어 있지만 앞의 온도가 높아질 지 낮아질지는 현재 시점에선 구할 수 없습니다. 그러나 Monotonic Stack은 현재 시점에서 과거 시점으로 되돌아가 계산할 수 있는 방법을 제공합니다.
temperatures = [73,74,75,71,69,72,76,73]
answer = [0] * len(temperatures)
stack = []
for current in range(len(temperatures)):
while stack and temperatures[stack[-1]] < temperatures[current]:
before = stack.pop() # 과거 날짜 불러오기
answer[before] = current - before # 날짜 차이
stack.append(current)
return answer
Monotonic Dequeue
Monotonic Dequeue는 Monotonic Stack과 똑같은 성질을 가지고 있습니다. 또한 Queue의 특징을 가지고 있어 과거의 저장한 데이터를 제거할 수 있습니다. 즉, 조건에 부합하지 않은 최소/최대 값은 제외함으로써 구간별 조건 계산에 특화되어 있습니다.
Sliding Window Maximum
정수배열
nums와 윈도우 길이인k를 주어질 때 각 sliding-window의최대값을 구하는 코드를 작성하시오.
슬라이딩 윈도우 별로 최대(혹은 최소)를 유지하면서 윈도우 범위가 넘어간 숫자를 동시에 제외해야 합니다. 이때 Monotonic Dequeue를 활용 할 수 있습니다.
최대값을 유지하기 위해 내림차순 Monotonic Dequeue를 생성하여 현재 인덱스의 최대값을 유지합니다. 이때 최대값을 저장한 제일 앞에있는 dequeue[0]와 현재 index의 차이를 계산하여 윈도우 사이즈를 넘으면 제외(dequeue) 시켜 다음으로 큰 값이 최대값이 되도록 성질을 유지시킵니다.
from collections import deque
nums = [1,3,-1,-3,5,3,6,7]
k = 3
decrease = deque()
answer = []
for right in range(len(nums)):
# decrease monotonic
while decrease and nums[decrease[-1]] < nums[right]:
decrease.pop()
decrease.append(right)
if decrease[0] + k == right:
decrease.popleft() # window-size를 넘어간 원소 제외
if right - k + 1 >= 0:
answer.append(nums[decrease[0]])
return answer
활용 사례
Monotonic dequeue는 (찾아보니) 활용사례가 꽤 있습니다. Monotonic Stack처럼 최근 n분간의 온도 측정, ddos차단 장비에서 n초간의 최대 패킷 개수를 탐지, n분간의 주가의 최대 최소값과 같은 문제들을 마주할 때 효과적으로 활용이 가능합니다.