모노톤 큐란 무엇인가: 슬라이딩 윈도우 최댓값 문제에서 왜 deque가 다시 등장할까

이 글의 목차 숨기기

마무리

모노톤 큐는 deque를 배운 뒤 한 번 더 넘어야 하는 심화 감각입니다. 단순히 앞뒤에서 넣고 빼는 구조를 아는 것만으로는 부족하고, 현재 구간에서 의미 있는 후보만 남겨야 하기 때문입니다.

이번 글에서는 모노톤 큐를 공식처럼 소개하지 않고, 슬라이딩 윈도우 최댓값 후보를 버리지 않고 잘 추려 남기는 구조로 설명하겠습니다. 특히 왜 deque를 쓰면서도 일반 deque 문제와 사고방식이 달라지는지까지 같이 보겠습니다.

기술적 개념 참고로는 cp-algorithms의 queue modification 설명을 볼 수 있습니다. 하지만 실전에서는 수식보다 후보를 언제 버리는지 감각이 더 중요합니다.

왜 일반 deque만으로는 부족할까

입문자가 많이 헷갈리는 지점은 deque를 쓴다는 사실만 보고 모노톤 큐도 그냥 양끝 삽입/삭제 문제라고 생각하는 것입니다. 하지만 모노톤 큐의 본질은 deque 연산 자체가 아니라, 후보를 정리하는 규칙을 유지하는 데 있습니다.

슬라이딩 윈도우 최댓값 문제에서는 단순히 현재 구간의 원소를 모두 들고 있는 것만으로는 부족합니다. 매번 최댓값을 다시 찾으면 결국 윈도우 크기만큼 다시 스캔해야 하므로 비효율적입니다.

즉 필요한 것은 현재 구간의 모든 원소가 아니라, 최댓값이 될 가능성이 있는 후보들입니다. 이 후보만 정리해서 들고 있으면 매번 전체를 다시 보지 않아도 됩니다.

모노톤 큐는 무엇을 유지하나

최댓값 문제 기준으로 보면, deque 안에는 값이 큰 순서가 유지되도록 후보를 넣습니다. 새로운 값이 들어올 때 뒤에 있는 더 작은 값들은 앞으로 최댓값이 될 수 없으므로 미리 제거합니다.

왜냐하면 더 늦게 들어온 값이 더 크다면, 더 먼저 들어온 작은 값은 남아 있어도 앞으로 그 큰 값을 이길 수 없기 때문입니다.

모노톤 큐 동작 흐름 그림 — 새 값이 들어올 때 뒤의 작은 후보를 정리하고, 앞에서는 만료된 후보를 제거하는 흐름

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # index 저장
    result = []

    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)

        if dq[0] <= i - k:
            dq.popleft()

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # index 저장
    result = []

    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)

        if dq[0] <= i - k:
            dq.popleft()

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result