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

💡 기본 개념

• 고정된 크기의 윈도우(구간)을 배열이나 문자열 위에서 일정 간격으로 이동시키며 문제를 해결하는 알고리즘 기법이다.
• 윈도우를 이동할 때 전체를 다시 계산하지 않고, 앞 요소는 빼고 새 요소만 더하는 식으로 누적 계산
• 시간복잡도는 O(n)

💡 언제 사용할까?

• 고정 길이의 부분 구간에서 최댓값, 최솟값, 합 등을 구할 때
• 투 포인터와 유사하지만, 윈도우 크기를 고정하거나 유동적으로 움직이는 문제에서 효과적이다.

 

✅ 예시: 고정 크기 부분합 최대값 구하기

def max_sum(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # 윈도우 이동
        max_sum = max(max_sum, window_sum)

    return max_sum

# 예시
print(max_sum([1, 2, 3, 4, 5, 6], 3))  # 출력: 15 (4+5+6)

# 1. 처음 윈도우 [1, 2, 3]의 합을 구한다.
# 2. 한 칸씩 이동하면서 맨 앞 값을 빼고 새로 들어오는 값을 더하며 최대합을 갱신한다.

 

💡 슬라이딩 윈도우 vs 투 포인터

항목슬라이딩 윈도우투 포인터

윈도우 범위	고정 또는 유동	유동
사용 예	최대합, 최장 길이, 조건 만족 구간	조건 만족 구간, 정렬된 배열 쌍 탐색
포인터 수	주로 2개(left, right)	2개(left, right)
차이점	윈도우 범위를 유지하며 이동	범위를 조절하면서 문제 해결