[Algorithm/Python] 슬라이딩 윈도우 알고리즘 정리

최근 기업 코테를 보며 자주 접했던 슬라이딩 윈도우에 대해 정리를 해보겠다.

(여태 3월 내 기업 코테에서 3번 정도 본 듯...)

 

슬라이딩 윈도우란?

일정한 크기의 윈도우를 배열이나 리스트 위에서 이동시키며 문제를 해결하는 기법

이 기법은 주로 연속된 부분 배열에서 최대 및 최소값, 특정 조건을 만족하는 구간 등을 찾는데 사용된다.

전체를 매번 계산하지 않고, 이전 값에서 변경된 부분만 계산해 효율을 높인다는 것을 기억하자!

 

기본 구조

누적합과 함께 쓸 때

arr = [3, 2, 1, 4, 5]
n = len(arr)

# 1. 누적합 배열 만들기
prefix_sum = [0] * (n + 1)
for i in range(n):
    prefix_sum[i+1] = prefix_sum[i] + arr[i]

# 2. 구간합 구하기 (예: 길이 k의 연속합 최대값)
k = 3
max_sum = 0
for i in range(n - k + 1):
    window_sum = prefix_sum[i + k] - prefix_sum[i]
    max_sum = max(max_sum, window_sum)

print(max_sum)

 

누적합 없이 쓸 때

(이전 값을 삭제하고 현재 값을 추가하여 중복된 계산은 재활용하며 진행)

arr = [1, 2, 3, 4, 5]
k = 3  # 윈도우 크기

window = sum(arr[:k])  # 초기 윈도우
max_sum = window

for i in range(k, len(arr)):
    window += arr[i] - arr[i-k]  # 윈도우 이동: 새 값 추가, 이전 값 제거
    max_sum = max(max_sum, window)

print(max_sum)

 

시간 복잡도

전체 배열을 한 번만 돌기 때문에 => O(n)