슬라이딩 윈도우

개요

‘슬라이딩 윈도우’는 부분 배열이나 부분 문자열과 같이, 어떤 ‘구간’과 관련된 문제를 해결하는 데 사용되는 기법이다.

동일한 원소를 반복적으로 순회하는 대신, 구간을 단계별로 이동시키면서 결과를 업데이트한다.

일반적으로 특정 조건을 만족하는 최대/최소 부분 배열 또는 부분 문자열을 찾는 문제에서 사용된다.

윈도우의 크기는 문제에 따라 고정되거나 고정되지 않을 수 있다.

예시

대표적인 문제로 크기가 k인 부분 배열의 최대합을 구하는 문제가 있다.

단순하게 생각하면 이중 반복문으로 모든 부분 배열의 합을 구해서 비교하는 방식으로 풀 수 있다. 이 경우 시간 복잡도는 $O(N^2)$이다.

슬라이딩 윈도우를 사용하면 $O(N)$의 시간 복잡도로 해결할 수 있다.

public int maxSum(int[] arr, int k) {
	int maxSum = 0;
	
	for (int i = 0; i < k; i++)
		maxSum += arr[i];
	
	int windowSum = maxSum;
	for (int i = k; i < arr.length; i++) {
		windowSum += arr[i] - arr[i - k];
		maxSum = Math.max(maxSum, windowSum);
	}
	
	return maxSum;
}

참고자료

• geeksforgeeks, Sliding Window Technique, 2025.09.02, https://www.geeksforgeeks.org/dsa/window-sliding-technique/