[Algorithm] 슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우

특정 범위(= 윈도우)가 주어질 때, 윈도우 내부 요소의 값을 이용해서 문제를 풀이하는 알고리즘

• 고정적인 범위를 탐색할 때, 유용하다.
• 중복으로 연산을 제거하면서 효율을 높일 수 있다.

최솟값 찾기

[문제]
N개의 수 A1, A2, ..., AN과 L이 주어진다.
Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램

import sys
from collections import deque
input = sys.stdin.readline
N, L = map(int,input().split())
num = list(map(int, input().split()))

temp = deque([]) # 최솟값 저장할 큐

for i in range(N):
  # 슬라이딩 윈도우 범위를 벗어나는 원소 삭제(당연히 맨 앞의 원소)
  if temp and temp[0][0] <= i-L:
    temp.popleft()

  # 들어올 원소가 기존의 원소보다 작으면 기존원소 삭제
  while len(temp) >= 1 and num[i] < temp[-1][1]:
    temp.pop()

  # 들어올 원소 추가
  temp.append((i,num[i]))
  
  # Di = Ai-L+1 ~ Ai 중의 최솟값
  print(temp[0][1], end = " ")

temp → [(i, num[i]), (i, num[i]), ..., (i, num[i])]