0. 알아볼 것

1. 슬라이딩 윈도우란?

길이가 N인 1차원 배열안에 길이가 W인 움직이는 구간을 생성하여, 해당 구간을 한 칸씩 움직이면서 구간 내 정보를 추출하여 문제를 해결하는 기술
(N과 W는 상수)

W인 구간을 움직이는 것이 마치 창문을 밀고 당기는 것과 같다고 하여, 움직이는 구간을 슬라이딩 윈도우라고 명명함.

2. 활용

(1) 구간합

1차원 배열에서 특정 구간 내의 합을 원하는 문제에서 활용.

a. 어떻게 활용?

배열의 길이가 N, 슬라이딩 윈도우의 길이가 W이고 해당 창문을 오른쪽으로 한 칸씩 움직인다면, 매 움직임 마다, 이전 위치에서의 W-1의 원소는 변하지 않고 구간 내에 유지된다. 예를 들어 N = 10, W = 3이라 가정하면,

그림과 같이 W-1인 2개의 원소는 변하지 않았다.
이를 활용해, 맨 처음 슬라이딩 윈도우를 만들 때만, 원소의 합을 일일히 더하여 구해놓고, 이후에는 구간이 움직이면서 빠지는 값을 빼고 추가되는 값은 더하면서, 구간합을 지속적으로 구할 수 있게 만드는 것이다.

b. 왜 활용?

슬라이딩 윈도우를 쓰지 않고, 길이가 N인 배열 내에서 길이가 W인 모든 구간의 구간합을 구한다고 가정해보자. 이 경우, 0번째 인덱스부터 W-1번 인덱스까지 일일히 값을 찾아내 더하고, 다시 1번부터 시작해 W번까지 조회하여 값을 더하고... 최악의 시간복잡도를 구해보면 O(NW)가 나오게 된다. (N = 구간의 시작점 찾기, W = 그 이후 구간 내의 원소 모두 조회)
반면, 슬라이딩 윈도우를 사용하면, 최초의 구간만 일일히 구하여 찾아내고, 그 후는 한 칸씩 움직이면서 최좌단의 원소는 뺄셈, 최우단의 원소는 덧셈해 나가면 된다. 이것은 매번 W번의 계산이 필요하던 것과 달리, 덧셈 한 번, 뻿셈 한 번이라는 고정된 계산만 하면 된다.(O(1)) 따라서 O(N)의 시간복잡도가 든다.