[Algorithm] 슬라이딩 윈도우

슬라이딩 윈도우란?

고정된 길이의 2개의 포인터 (커서)를 같이 움직이면서 O(N)에 배열을 탐색하는 테크닉

N개의 원소를 갖는 배열이 있고, W의 넓이를 갖는 창문이 있다고 가정하자. (N, W는 고정된 상수)

• 창문을 왼쪽부터 시작해서 한 칸씩 오른쪽으로 이동시켜야 한다.
• 이동시킬 때마다 창문 안에서의 정보 유출 (ex. 합)이 필요하다.

 

아래 예시는 원소의 개수가 10개이면서 윈도우 크기가 3일 때이다.

 

문제에서 대놓고 슬라이딩 윈도우라고 언급할 때도 있지만, 몇몇 문제들은 언급 없이 슬라이딩 윈도우 테크닉을 써야할 때가 있다.

 

 

💡 슬라이딩 윈도우의 기본 아이디어

• 윈도우를 한 칸 옮기면 (W-1)칸은 겹친다.
• 이전에 내가 구해야 하는 창문의 형태와 다음 상태 사이에서 중복된 정보가 W-1개 있으므로 이를 최대한 활용하자!

 

원래대로라면, 윈도우를 옮길 때마다 3개의 숫자를 일일히 더해야 한다.

그렇게 하지 않고, 겹치는 구간에 대한 결과를 최대한 사용하도록 하자.

이렇게 하면 O(1)만에 두번째 윈도우에 대한 결과를 알 수 있다.

 

 

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

 

슬라이딩 윈도우 아이디어를 적용하면,

맨 처음 창문에 대해서만 O(W)이고, 이후에 한 칸씩 밀 때에는 O(1)에 구간 합을 구할 수 있다.

결국 전체 시간 복잡도는 O(N)이 된다.

 

예시) 연속된 3개의 합 중 최댓값을 구하는 프로그램 작성하기

7개의 a0, a1, a2, … , a6으로 이루어진 수열이 있다. 이 수열에서 연속된 3개의 값의 합 중 최댓값을 구하는 프로그램을 작성하시오.

 

 

이를 완전 탐색으로 푼다면 다음과 같다.

int answer = 0;

for (int i = 0; i <= n - m; i++) {
	int sum = 0;

	for (int j = 0; j < m; j++) {
		sum += a[i + j];
		answer = max(answer, sum);
	}
}

시간 복잡도는 N개의 수열에서 연속된 M개의 값 중 최댓값을 찾은 경우라면 O(NM)이다.

 

 

슬라이딩 윈도우 하는 방법

1. 윈도우의 사이즈를 정한다.
2. 첫번째 윈도우에서 값을 계산한다.
3. 첫번째 계산값을 기반으로 윈도우를 옮겨가며 값을 갱신한다.

 

위 방법을 앞의 예제에 적용하면 다음과 같다.

 

 

1. 윈도우의 사이즈를 정한다. ⇒ 연속된 3개의 값을 봐야하므로, 윈도우 크기 = 3

2. 첫번째 윈도우에서 값을 계산한다. ⇒ a[0] + a[1] + a[2] = 9이다.

3. 첫번째 계산값을 기반으로 윈도우를 옮겨가며 값을 갱신한다.

• 현재 값에서 a[leftPointer]를 빼주고 left를 증가시킨다.
• right를 증가시킨 후, 현재 값에 a[rightPointer]를 더해준다.

answer = max(answer, current);

current -= a[leftPointer];
leftPointer += 1;
rightPointer += 1;
current += a[rightPointer];

 

 

자세한 과정은 다음과 같다. 

 

leftPointer	rightPointer	a[leftPointer] + a[rightPointer]
0	2	9
1	3	13
2	4	10
3	5	13
4	6	7
5	7	종료!

 

시간 복잡도 분석

원소의 개수가 n개인 배열에서 윈도우의 크기가 m일 때, rightPointer가 m-1번째 인덱스부터 n번째 인덱스까지 움직인다. 그렇기 때문에 O(N-M)이고, 보통 N > M이므로 O(N)이라고 한다.

int leftPointer = 0;
int rightPointer = m - 1;
int answer = 0;
int current = 0;

while (rightPointer < N) {
	answer = max(answer, current);
	current -= a[leftPointer];
	leftPointer += 1;
	rightPointer += 1;
	current += a[rightPointer];
}

 

투포인터 알고리즘과의 차이

• 투포인터 알고리즘 → 구간이 가변적 길이
• 슬라이딩 윈도우 → 구간이 고정적 길이

 

관련 문제들

백준 12847번

추가로 업데이트 예정~!

 

 

[알고리즘 강의] Sliding Window, 슬라이딩 윈도우