슬라이딩 윈도우(Sliding Window) 알고리즘

슬라이딩 윈도우란?

슬라이딩 윈도우 알고리즘은 투 포인터 알고리즘과 유사하게 부분 배열들을 활용하는 알고리즘이다.

투포인터와 다른 점은 부분 배열의 길이(크기)가 고정적이다. 그래서 포인터 변수가 2개일 필요가 없다.

 

이름 그대로 고정적인 너비를 가진 창문을 두고 옆으로 한칸씩 이동하며 값을 구하는 방법이다.

 

예를들어, N개의 원소를 갖는 배열이 있다. 이때 W의 너비를 갖는 창문이 있다.

너비가 3인 창문을 제일 왼쪽에 배치하고, 창문을 왼쪽에서 시작하여 한 칸씩 오른쪽으로 이동한다.

매 순간 창문 안에서의 정보를 활용해 유추해서 값을 구한다. 

 

즉, 같은 너비의 연속 구간들을 연속적으로 처리할 때 주로 사용되는 테크닉이다. 인접한 구간들 사이에 겹치는 정보를 최대한 활용하는 것이 포인트다.

 

관련 문제 및 응용 방법

1. 구간 합

문제 : N개의 숫자, 창문의 크기 W가 주어졌을 때, 왼쪽부터 W개씩 연속 합을 모두 구하라. (N = 8, W = 3)

 

슬라이딩 윈도우의 기본 아이디어는 Window를 한 칸 옮기면 (W-1)칸은 겹친다는 것이다. 중복된 것을 활용하자.

기존 방법이었다면 매순간 3개씩 숫자 다 더해야했다. 창문을 옮길 때마다 W개를 전부 다 더하는 작업을 하지 말고, 이전의 결과를 써먹는 방향으로 접근하자.

기존에는 모든 창문 위치마다 O(W)에 합을 구해서 전체가 O(NW)의 시간 복잡도를 가졌다.

슬라이딩 윈도우의 아이디어를 적용하면, 맨 처음 창문에 대해서만 O(W)이고, 이후에 한 칸씩 밀 때에는 O(1)에 구간 합을 구할 수 있다. 결국 전체 시간 복잡도는 O(N)이 된다.

 

 

2. Anagram(아나그램)

아나그램(Anagram)이란, 알파벳의 구성은 유지한 채, 순서만 뒤바뀐 단어 관계를 의미한다.

ex) listen ↔ silent

 

문제: 문자열 2개 S1, S2 가 주어진다. S2의 부분 문자열 중, S1과 anagram 관계인 것의 개수를 구하는 문제

문제를 풀려면 창문에 보이는 알파벳의 구성이 S1과 똑같은지 봐야한다.

마찬가지로, 모든 창문의 위치마다 알파벳 개수를 세면 O(W)라는 시간을 소모하지만, Sliding Window의 아이디어를 사용하면 알파벳 개수 업데이트에 드는 시간을 O(1)로 줄일 수 있다.

 

 

그 외에도 구간 최솟값 문제를 풀 수 있다(백준 11003번 문제)

해당 문제는 dec, deq 아이디어도 알아야 풀 수 있다고 한다.

 

 

 

 

참고 : IOI KOREA님의 알고리즘 강좌