슬라이딩 윈도우 (Sliding window)

✅ 알고리즘 문제에서 연속된 구간(부분 배열/부분 문자열 등)을 효율적으로 탐색할 때 자주 사용되는 핵심 기법,

특히 시간복잡도를 줄이기 위해 반복 계산을 피하고 누적값을 활용할 때 매우 유용하다.

고정된 크기 혹은 조건을 만족하는 "연속된 구간"을 윈도우로 보고,

이 윈도우를 한 칸씩 움직이면서 효율적으로 결과를 계산한다.

 

🔍 왜 쓰는가?

문제 상황 예시:

• 배열에서 길이 K짜리 부분합의 최댓값 구하기
• 문자열에서 연속된 알파벳 중 중복 없이 가장 긴 부분 문자열
• 투 포인터로 특정 합을 만족하는 구간 찾기

이런 경우, 단순히 매번 구간을 순회하면 시간 복잡도가 O(NK), 하지만 슬라이딩 윈도우를 쓰면 O(N)으로 줄일 수 있다.

 

📌 기본 원리

1. 처음 구간(window)을 먼저 계산해 초기값 설정
2. 이후 한 칸씩 오른쪽으로 윈도우를 밀면서,
   • 앞쪽 요소 제거
   • 뒤쪽 요소 추가
3. 이 과정을 반복하면서 누적값, 최대값, 조건 등을 갱신

 

✍️ 예시 1: 고정 길이 부분합 최대값

문제: 배열 arr에서 길이 k인 연속된 부분 배열의 합 중 최댓값 구하기

def max_sliding_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

• 시간복잡도: O(N)
• 핵심: 매번 sum() 안 하고, 직전 합에서 앞 요소 빼고 뒤 요소 더하는 방식

 

✍️ 예시 2: 중복 없는 가장 긴 부분 문자열 (투 포인터 활용)

문자열 s에서 중복 없는 가장 긴 부분 문자열의 길이

def length_of_longest_substring(s):
    seen = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

• 윈도우: s[left:right+1]
• 윈도우 안에 중복이 없도록 유지 → 조건 만족하는 구간 유지
• 시간복잡도: O(N)

 

🧠 언제 쓰면 좋은가?

패턴	설명	예시 문제
고정된 길이의 부분합	한 칸씩 이동하며 합/최댓값 갱신	길이 K의 최대 부분합
특정 조건을 만족하는 구간	윈도우를 줄였다 늘리며 조건 만족	투 포인터: 합이 M인 구간 수
문자열 탐색	중복 제거/조건 유지	가장 긴 중복 없는 부분 문자열

 

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

• 슬라이딩 윈도우는 윈도우의 시작/끝을 한 칸씩 움직이며 상태를 유지
• 투 포인터는 더 일반적으로 왼쪽/오른쪽 포인터를 조건에 따라 따로 조절하는 방식

사실상 슬라이딩 윈도우는 투 포인터의 한 특수한 형태라고 보면 된다!

 

✅ 정리

특징	설명
핵심 아이디어	윈도우(구간)를 유지하며 한 칸씩 이동
장점	반복계산 없이 누적값, 조건, 개수 등을 효율적으로 관리
시간복잡도	대부분 O(N)
자주 쓰이는 곳	누적합, 부분 문자열, 조건 만족 구간 찾기