[알고리즘] 슬라이딩 윈도우

슬라이딩 윈도우

슬라이딩 윈도우란 고정된 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다. 투 포인터와 유사하지만 일반적으로 고정 사이즈 윈도우를 사용하는 경우 슬라이딩 윈도우를 구분한다. 또한, 투포인터는 주로 정렬된 리스트를 대상으로 하지만 슬라이딩 윈도우는 정렬 여부에 관계 없이 사용 가능하다.

예시

[1, 5, -3, 6, 10, -14, -2] 라는 배열이 있는데 연속적인 4개의 숫자의 합이 최대인 값을 찾는 경우를 들 수 있다.

부분 리스트	합
[1, 5, -3, 6], 10, -14, -2	9
1, [5, -3, 6, 10], -14, -2	18
1, 5, [-3, 6, 10, -14], -2	-1
1, 5, -3, [6, 10, -14, -2]	0

구현

array=[1, 5, -3, 6, 10, -14, -2]
n = len(array)
size=5
window=sum(array[:size])
answer=window

for i in range(size, n) :
		window += array[i] - array[i-size]
		answer=max(answer, window)

print(answer)