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

슬라이딩 윈도우 알고리즘이란

1,2,3,4,5 라는 숫자 배열이 있다.
이 안에서 A[i] + A[i+1] + A[i+2]라는 형식으로 연속적인 3개의 숫자 합을 구하려고 한다.

[1,2,3],4,5 / 1,[2,3,4],5 / 1,2,[3,4,5]

이런 식으로 창문이 창틀을 따라서 미끄러지듯 일정한 크기의 윈도우가 틀을 만들어 이동하는 것을 볼 수 있다.
이러한 특성으로 인해, 크기가 n인 연속된 부분 합을 구하는 경우 자주 사용된다.

 

투 포인터와 슬라이딩 윈도우의 차이

두 알고리즘은 모두 부분 배열의 합(prefix sum)을 구하는 데 유용하게 사용된다. 

투 포인터

•  구간의 길이를 가변적으로 잡는다.
• 구간의 양쪽 끝이 되는 포인터가 두 개 필요하다.(시작, 끝)

슬라이딩 윈도우

• 합을 구할 부분집합의 개수가 정해져있다. = 구간의 길이가 정해져있다.
• 포인터가 두 개일 필요가 없다.

 

주요 코드

num =[ 1,2,3,4,5]
k = 3

window = sum(num[:k])
answer = window

for i in range(3, n):
	window = window +num[i] - num[i-k]
    answer = max(window, answer)

num이라는 숫자 배열이 있다고 할 때, 3까지의 고정 틀 안의 숫자들을 합해놓는다. 그리고 이 window를 천천히 뒤로 하나씩 움직이면서 연산을 진행할 것이다.

3까지 이미 계산해놓았으니, for문은 4번째 자리(num[3])부터 시작한다.

그리고 한칸씩 뒤로 가면서 i번째 수는 더해주고, i-k번째 수는 빼주는 식으로 진행한다.

이렇게 진행하면 배열에서의 가장 큰 부분합을 구할 수 있다.

 

관련 문제

문제집

문제집: 슬라이딩윈도우/투포인터 (haru8986)

 

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

https://www.acmicpc.net/problem/12891

12891번: DNA 비밀번호

 

https://www.acmicpc.net/problem/3078

3078번: 좋은 친구