슬라이딩 윈도우

슬라이딩 윈도우는 배열이나 리스트 요소의 일정 범위 값을 비교할 때 시간 복잡도를 줄이는 알고리즘이다.

구간, 연속된 등의 키워드가 보인다면 슬라이딩 윈도우를 떠올려보자.

슬라이딩 윈도우의 설명

슬라이딩 윈도우는 투 포인터와 유사하게 동작한다.
유사하게 동작한다고는 하지만 투 포인터를 활용한다고 봐도 된다.

투 포인터 vs 슬라이딩 윈도우

투 포인터는 두 개의 포인터를 입맛대로 이동시키면서 원하는 값을 얻는 알고리즘이다.
슬라이딩 윈도우는 포인터를 입맛대로 이동시킬 수 없다.

두 포인터 간의 간격은 항상 유지되어야 한다.
이때 두 포인터가 동시에 움직이는 모습이 마치 창문과도 같다.

교집합의 활용

두 포인터가 고정된 넓이를 가진 채, 한 방향으로 이동하다 보면 교집합이 발생한다.
포인터가 이동할 때마다 윈도우 크기 - 1만큼 겹치기 때문이다.

즉, 이를 잘 활용하면 구간의 합이나 원하는 결과물을 O(1)로 얻어낼 수 있다.
물론 처음 윈도우를 생성할 때는 시간 복잡도가 O(n)이다.

슬라이딩 윈도우의 예시

배열 A 내부의 연속된 3개 원소의 합으로 10을 구성하는 경우의 수를 구한다고 해보자.
A = {1, 2, 3, 7, 4, 6, 5, 8}

| | 은 창문을 표현한다.

| 1 2 7 | 3 4 6 5 8
S = 1 + 2 + 7 = 10

1 | 2 7 3 | 4 6 5 8
S = S + A[eidx + 1] - A[sidx - 1]
S = 10 + 3 - 1 = 12

1 2 | 7 3 4 | 6 5 8
S = 12 + 4 - 2 = 14

1 2 7 | 3 4 6 | 5 8
S = 14 + 6 - 7 = 13

1 2 7 3 | 4 6 5 | 8
S = 13 + 5 - 3 = 15

1 2 7 3 4 | 6 5 8 |
S = 15 + 8 - 4 = 19

즉, 만족하는 경우는 1 + 2 + 7로 1가지이다.