[ 슬라이딩 윈도우 ] 슬라이딩 윈도우 이론 정리

1. 슬라이딩 윈도우란?

슬라이딩 윈도우(Sliding Window) 알고리즘은 고정된 크기 또는 가변 길이의 부분 구간(subarray) 을 배열이나 문자열에서 연속적으로 이동시키면서 특정 값을 계산하는 기법입니다.

이름 그대로 "창문(window)"을 왼쪽에서 오른쪽으로 조금씩 밀면서 처리한다는 의미로,
매번 전체 범위를 새로 계산하지 않고 이전 결과를 재활용하여 효율적으로 처리할 수 있습니다.

 

 

2. 언제 사용하는가?

슬라이딩 윈도우는 다음과 같은 경우에 주로 사용됩니다:

• 고정 길이 구간의 최댓값, 최솟값, 합 등을 구하는 문제
• 가변 길이 구간에서 어떤 조건을 만족하는 최소/최대 구간 찾기
• 문자열에서 중복 문자 없는 가장 긴 부분 문자열 찾기
• 일정 범위 내에서 조건이 유지되는 구간 탐색

 

3. 슬라이딩 윈도우 동작 방식

1) 고정 길이 윈도우

정해진 길이 k만큼의 윈도우를 좌우로 밀어가며 합이나 평균 등을 구함

arr = [1, 3, 2, 6, 4, 5]
k = 3

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

for i in range(k, len(arr)):
    window_sum = window_sum - arr[i - k] + arr[i]
    max_sum = max(max_sum, window_sum)

 

• 핵심: 새 구간 = 이전 구간 - 맨 앞 값 + 맨 뒤 값
• O(N) 시간에 전체 탐색 가능

2) 가변 길이 윈도우 (조건 만족하는 구간 탐색)

조건을 만족하지 않으면 오른쪽 포인터(end)를 늘리고,
조건을 초과하면 왼쪽 포인터(start)를 줄이는 구조

arr = [1, 2, 3, 2, 5]
target = 7

start = 0
current_sum = 0
min_length = float('inf')

for end in range(len(arr)):
    current_sum += arr[end]

    while current_sum >= target:
        min_length = min(min_length, end - start + 1)
        current_sum -= arr[start]
        start += 1

 

• start, end는 모두 오른쪽으로만 이동
• 구간 길이가 유동적일 때 유용

3) 원형 배열 슬라이딩 윈도우 (회전초밥 문제)

일반 슬라이딩 윈도우는 배열 끝에 도달하면 끝이지만,
원형 배열에서는 끝에서 다시 처음으로 이어지기 때문에 인덱스를 순환(circular) 시켜야 한다.
이런 구조는 모듈로 연산 (%)으로 쉽게 구현할 수 있음.

 

 

 

4. 구현 팁

• 누적합을 한 번 계산한 뒤, 그걸 바탕으로 윈도우를 조정하면 시간 복잡도를 줄일 수 있음
• 매번 전체 구간을 다시 계산하지 않기: 슬라이딩 윈도우의 핵심은 재활용
• 가변 길이인 경우, 조건 만족 여부에 따라 start를 조정해야 함
• 문자열에서는 set이나 dict를 활용해 중복 여부나 등장 횟수를 관리할 수 있음