[Python] 슬라이딩 윈도우

슬라이딩 윈도우

고정 크기의 윈도우를 이동하면서 윈도우 내의 요소들의 값을 이용하여 문제를 해결하는 알고리즘

• 투 포인터와 유사한 알고리즘이지만, 슬라이딩 윈도우는 고정된 구간을 탐색함
• 정렬 여부에 관계 없이 사용 가능함
• 단방향 포인트 이동
• 전체 탐색(반복문)은 O(N^2), 슬라이딩 윈도우를 사용하면 O(N)

빈출 예제 : 연속적인 N개의 숫자의 합의 최댓값 구하기

1. 리스트 입력 받기
2. window에 0 ~ (N-1) 인덱스 까지의 합으로 초기화
3. N번 인덱스부터 탐색을 진행
4. window에 현재 인덱스를 더하고 현재 인덱스의 -N를 한 인덱스를 뺀다
5. 계산 후 최댓값을 출력한다.

예제 코드

numbers = [1, 5, 3, 7, -3, 1, 9]
n = 5

window = sum(numbers[:n])
answer = window

for i in range(n, len(numbers)):
	window += numbers[i] - numbers[i - n]
    answer = max(answer, window)
    
print(answer)