슬라이딩 윈도우

📚 '슬라이딩 윈도우' 란

• 투포인터와 매우 비슷한 알고리즘으로 주어진 자료구조를 순차적으로 이동해가면서 연산을 수행 (일반적으로는 부분합을 구함)
• 리스트안에 윈도우(특정 범위)가 있을때 내부 요소의 값을 이용하여 문제를 풀이

  

📝 개념 정리

슬라이딩 윈도우는 어떠한 배열에서 고정된 크기의 범위를 탐색할 때 유용
아래와 같은 배열이 있을 때 k = 3 크기의 슬라이딩 윈도우를 사용해 최대값을 구하려고 한다.

그럼 아래와 같이 윈도우가 움직이며 그 안의 값들의 합을 구할 것 이다. `1 + 3 + 2`의 값을 구한 뒤 움직여 `3 + 2 + 6`의 값을 구하게 되는데 `3 + 2` 가 중복되게 된다.

중복된 값이 나오는 점을 이용하여 윈도위의 합을 계산해 보면,

처음의 `(1 + 3 + 2)`의 값에서 윈도우에서 빠지게 되는 1의 값을 빼주고 6을 더해주면 처음 윈도우의 합을 이용해 두번째 윈도우의 값을 구할 수 있게 된다!!!

💻 코드 구현

temp = [1, 3, 2, 6, -1, 4]
N = len(temp)
K = 3

total = sum(temp[:K])
max_total = sum_temp

for i in range(K, N):
	total -= temp[i-K]
    total += temp[i]
    
    max_temp = max(max_total, total)

• total 에 0 ~ 2번 인덱스의 값을 저장 → 1+3+2
• K번째인 3번째 인덱스부터 탐색 진행
• total에서 i-K인 temp[0] 값을 빼주기! → total - 1 = 3+2
• total에 현재 인덱스 값인 temp[3] 더하기 → total + 6 = 3+2+6