슬라이딩 윈도우 (Sliding Window)

정의

슬라이딩 윈도우 (Sliding Window) 는 배열/문자열 위에서 고정 크기 또는 가변 크기 윈도우가 한 방향으로 미끄러지며 각 윈도우마다 조건 (합, 최댓값, 중복 여부 등) 을 체크하는 정형. 두 포인터 (l, r) 로 윈도우 경계를 유지하며 O(N) 에 전체 구간 탐색.

역사: 두 포인터 기법의 자연스러운 확장. 1990년대 문자열 패턴 매칭 (rolling hash, Rabin-Karp) 과 함께 정립.

문제 상황과 동기

“연속 부분 배열/문자열 중 조건 만족하는 것 찾기”.

• naive: 모든 시작점 l 에 대해 끝점 r 을 늘려가며 탐색. O(N^2). N=10^5 이면 10^10, 불가능.
• sliding window: 윈도우를 한 칸씩 이동. 각 원소는 최대 2번 (추가 1번, 제거 1번) 만 접근. O(N).

핵심 통찰: 이전 윈도우 정보를 재사용. [l, r] 에서 [l+1, r+1] 로 이동 시 a[l] 제거, a[r+1] 추가만 하면 됨.

자주 등장:

• 고정 크기: 길이 K 윈도우의 최대 합, 평균, 최댓값.
• 가변 크기: “합 ≤ S 인 최장 구간”, “중복 없는 최장 부분 문자열”, “조건 만족하는 최소 구간”.

시각화

핵심 아이디어

invariant: 윈도우 [l, r] 이 조건을 만족 (또는 위반) 하는 최대/최소 구간.

고정 크기 K:

초기 윈도우 [0, K-1] 계산
for r = K..N-1:
    윈도우에 a[r] 추가
    윈도우에서 a[r-K] 제거
    조건 체크

가변 크기 (예: 합 ≤ S):

l = 0, sum = 0
for r = 0..N-1:
    sum += a[r]
    while sum > S:
        sum -= a[l]
        l++
    조건 만족: [l, r]

확장:

• deque: 윈도우 최댓값/최솟값을 O(1) 에 유지 (monotonic deque).
• hash/set: 중복 체크 O(1).
• two pointer 와 차이: sliding window 는 윈도우 크기/조건 유지에 집중. two pointer 는 더 일반적 (양 끝에서 좁히기, 정렬 필요 등).

알고리즘 (고정 크기 K, 최대 합)

max_sum_k(a, K):
    sum = Σ a[0..K-1]
    max_sum = sum
    for r = K..N-1:
        sum += a[r]
        sum -= a[r - K]
        max_sum = max(max_sum, sum)
    return max_sum

시간: O(N). 각 원소 1번씩만 접근.

구현

// 고정 크기 K, 최대 합
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k; cin >> n >> k;
  vector<int> a(n);
  for (auto& v : a) cin >> v;
  long long sum = 0;
  for (int i = 0; i < k; i++) sum += a[i];
  long long mx = sum;
  for (int r = k; r < n; r++) {
      sum += a[r];
      sum -= a[r - k];
      mx = max(mx, sum);
  }
  cout << mx << "\n";
}

# 고정 크기 K, 최대 합
import sys
input = sys.stdin.readline
​
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a[:k])
mx = s
for r in range(k, n):
  s += a[r]
  s -= a[r - k]
  mx = max(mx, s)
print(mx)

// 고정 크기 K, 최대 합
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken());
      int[] a = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
      long sum = 0;
      for (int i = 0; i < k; i++) sum += a[i];
      long mx = sum;
      for (int r = k; r < n; r++) {
          sum += a[r];
          sum -= a[r - k];
          mx = Math.max(mx, sum);
      }
      System.out.println(mx);
  }
}

5 3
1 2 3 4 5

12

설명: 길이 3 윈도우. [1,2,3]=6, [2,3,4]=9, [3,4,5]=12. 최댓값 12.

가변 크기 예제 (합 ≤ S, 최장 구간)

// 합 ≤ S 인 최장 구간 길이
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, s; cin >> n >> s;
  vector<int> a(n);
  for (auto& v : a) cin >> v;
  int l = 0, mx = 0;
  long long sum = 0;
  for (int r = 0; r < n; r++) {
      sum += a[r];
      while (sum > s) {
          sum -= a[l];
          l++;
      }
      mx = max(mx, r - l + 1);
  }
  cout << mx << "\n";
}

# 합 ≤ S 인 최장 구간 길이
import sys
input = sys.stdin.readline
​
n, s = map(int, input().split())
a = list(map(int, input().split()))
l = 0
mx = 0
cur = 0
for r in range(n):
  cur += a[r]
  while cur > s:
      cur -= a[l]
      l += 1
  mx = max(mx, r - l + 1)
print(mx)

5 7
1 2 3 4 5

3

설명: 합 ≤ 7. [1,2,3] 합 6 (길이 3), [1,2,3,4] 합 10 (초과), [2,3] 합 5 (길이 2), [4] 합 4 (길이 1), [5] 합 5 (길이 1). 최장 길이 3.

복잡도

변형 / 활용

함정

1. 윈도우 초기화 실수

고정 크기 K 일 때 초기 윈도우 [0, K-1] 을 먼저 계산 안 하고 바로 r=K 부터 시작하면 첫 윈도우 누락.

2. 가변 크기에서 l 포인터 조건 잘못

while (sum > S) 가 아니라 if (sum > S) 로 쓰면 윈도우가 제대로 줄어들지 않음. 반드시 while 로 조건 만족할 때까지 l 증가.

3. r - l + 1 vs r - l

구간 길이는 r - l + 1 (inclusive). r - l 로 쓰면 1 차이.

4. overflow

N=10^5, 원소 10^6 이면 합이 10^11. C++ 에서 int 는 ~2×10^9 까지. long long 필요.

BOJ 연습 문제

참고

• 두 포인터
• 누적 합
• 덱 (monotonic deque 로 윈도우 최댓값)
• 해시 테이블 (중복 체크)