슬라이딩 윈도우란, N개의 원소를 갖는 배열에서, W의 넓이를 갖는 창문이 계속해서 이동하는 것이다. 특정 구역의 합계나 평균을 구하는데 유용하게 사용된다. 계산해야할 데이터가 많다면 매 구간마다(창문마다) 최대/최소/합계를 새로 구하는 것은 `O(NW)`의 시간 복잡도를 갖게 되고, 너무 오래걸리게 된다. 이런 경우 슬라이딩 윈도우가 유용하게 사용된다.
✔️ 짚어가기: 슬라이딩 윈도우 프로토콜
슬라이딩 윈도우는 패킷 기반 데이터 전송 프로토콜을 의미하기도 한다. 데이터 링크 계층(OSI 2계층)이나 전송 제어 프로토콜(TCP)와 같이 패킷의 안정적인 순차적 전송이 필요한 경우에 사용된다. 데이터 전달을 보증하기 위해서는 확인 신호(ACK)를 받아야 하는데, 패킷이 중도에 분실되는 경우, 해당 패킷을 재전송 해야한다. 슬라이딩 윈도우는 일단 윈도우(메모리 버퍼의 일정 영역)에 포함되는 모든 패킷을 전송하고, 패킷의 전달이 확인대는 대로 이 윈도우를 옆으로 옮김(slide)으로서 그 다음 패킷을 전송하는 방식이다. 슬라이딩 윈도우는 확인(ACK)을 받지 않고도 여러 패킷을 보낼 수 있기 때문에, stop-and-wait 방식보다 네트워크를 더 효율적으로 사용할 수 있다.
✔️ 슬라이딩 윈도우 알고리즘의 아이디어
Sliding Window
슬라이딩 윈도우의 기본 아이디어는 'Window를 한 칸 옮기면 (w-1)칸은 겹친다! '라는 것이다. 쉽게 말해, 윈도우를 옮길 때마다 중복되는 값이 존재하고, 이를 활용하여 목표 값을 좀 더 빠르게 찾는 것이다. 예를 들어, 합계를 구해야 할 때, 전에 구한 값에 윈도우를 벗어난 값을 빼고, 새로 들어올 값을 더해주면 되는 것이다. 위의 그림에서, `W1`의 값은 `13`이고, `W2`의 값은 `13-1+3=15`, W3의 값은 15-5+4=14이다. 이런 방식으로 계산하면 굳이 배열을 다시 순회할 필요 없이 `O(1)`로 구하고자 하는 값을 구할 수 있다. 이러한 방식은 배열과 윈도우의 크기가 커질수록 유리하다.
💡정리
기존에는 모든 창문마다 O(W)에 새로이 합을 구했다.
이 경우, 배열 전체를 계산하려면 O(NW)의 시간 복잡도를 가진다.
Sliding Window의 아이디어는 'Window를 한 칸 옮기면 중복값이 존재한다'이다.
이를 적용하면 맨 처음 창문에 대해서만 O(W)이고, 이후 윈도우를 한 칸씩 밀 때에는 O(1)에 구간합을 구할 수 있다.
따라서, 전체 시간 복잡도는 `O(N)`이다.
🎯 관련 문제
슬라이딩 윈도우 관련 문제로는 아나그램, 구간합, 구간 최솟값, 구간 최댓값을 구하는 문제가 있다.
🤔Anagram이란? 아나그램(Anagram)이란, 알파벳의 구성은 유지한 채, 순서만 뒤바뀐 단어 관계를 의미한다. 예시로는 listen과 silent가 있다. 아나그램 문제의 예시로는 문자열이 2개 주어질 때(S1, S2), S2의 부분 문자열 중, S1과 anagram관계인 것의 개수를 구하는 문제가 있다. anagram question
백준 11003번 문제(BOJ11003)
슬라이딩 윈도우 문제인 백준 11003번을 풀어보자! 구간 최솟값을 구하는 문제이다. 주어지는 값이 최대 5백만으로 꽤 크기 때문에, `min()`함수를 이용한 완전탐색 방식으로는 풀 수 없다. 따라서 슬라이딩 윈도우를 사용해보자.
문제 풀이 순서는 1) 알고리즘과 자료구조 힌트만 보고 구조를 짠다 (약 15분 투자) → 코드를 짠다(약 30분) 2) 구조가 생각나지 않는다면 아래 문제풀이 아이디어를 보고 코드를 짠다 (약 30분) 3) 아이디어가 이해되지 않는다면 코드를 보고 따라 써 본다. 3-1. 코드를 따라 구간 최솟값을 직접 계산해본다. 3-2. 코드를 이해했다면 보지 않고 처음부터 다시 작성해본다.
from collections import deque
import sys
input = sys.stdin.readline
N, L = map(int, input().split()) # 배열의 크기, 윈도우 크기
arr = list(map(int, input().split()))
q = deque()
D = []
for i in range(N):
while q and arr[q[-1]] > arr[i]: # 큐에 값이 있고, top이 현재 값보다 크다면
q.pop() # 삭제한다
q.append(i) # 현재 값의 인덱스를 저장한다.
if q[0] <= i - L: # 최솟값이 윈도우 크기를 벗어난다면
q.popleft() # 삭제한다
D.append(arr[q[0]]) # 최솟값 저장
print(" ".join(D)) # 결과 출력
