Sliding-window 기법은 배열이나 문자열 위에 연속된 범위(윈도우)를 유지하고, 처음부터 다시 계산하는 대신 윈도우를 미끄러뜨려 많은 부분 배열/부분 문자열 문제를 **O(n)**으로 해결합니다.
개념
오른쪽 끝을 이동하여 윈도우를 확장하고, 제약이 위반되면 왼쪽 끝을 이동하여 축소합니다. 다시 스캔하는 대신 이전 계산을 재사용합니다.
예시: 크기 k인 임의 윈도우의 최대 합
python
def max_window_sum(arr, k):
window = sum(arr[:k]) # 첫 윈도우의 합
best = window
for i in range(k, len(arr)):
window += arr[i] - arr[i - k] # 새 값 더하고 오래된 값 뺌
best = max(best, window)
return best
max_window_sum([2, , , , , ], )
복잡도
- 시간: O(n) — 각 원소가 윈도우에 한 번 들어오고 한 번 나갑니다.
- 공간: 고정 윈도우는 O(1), 내용을 추적할 때는 O(k).
언제 사용하나 / 함정
"속성 X를 만족하는 가장 긴/가장 짧은/최대 부분 배열" 문제에 사용하세요. 가변 윈도우의 경우 왼쪽 포인터를 전진시켜 제약을 복원합니다. 경계 원소를 더하거나 뺄 때 off-by-one 오류를 주의하세요.
왜 중요한가
Sliding window는 중복 작업을 제거하여 O(n·k) 재계산을 한 번의 순회로 바꿉니다.
면접에 끊임없이 등장하는 부분 문자열과 부분 배열 문제의 핵심 패턴입니다.
재계산 대신 이전 결과를 재사용한다는 통찰은 스트리밍과 실시간 데이터로 일반화됩니다.