슬라이딩 윈도우 알고리즘(Sliding Window Algorithm)은 배열과 같은 선형 자료구조에서 연속된 구간 내의 데이터를 효율적으로 처리하기 위해 사용하는 기법이다. 특히 배열 내 연속된 요소의 합, 최대값, 최소값 등을 계산할 때 유용하다.
슬라이딩 윈도우는 이름 그대로 고정/가변 크기의 범위(윈도우)를 이동(슬라이드) 시키면서 필요한 계산을 반복하는 방식이다. 이때 전체 배열을 한 번만 순회하면 되기 때문에 중복 연산을 피하고 시간 복잡도를 개선할 수 있다. 일반적으로 슬라이딩 윈도우 기법을 사용하면 O(n)의 시간 복잡도로 문제를 해결할 수 있다.
// 주어진 배열에서 연속된 k개 요소의 최대 합을 찾는 함수
function maxSumSubarray(arr, k) {
let maxSum = 0;
let windowSum = 0;
// 초기 윈도우(k개의 요소) 합 계산
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
// 슬라이딩 윈도우 이동
for (let end = k; end < arr.length; end++) {
const start = end - k;
// arr[end]가 새로 추가되는 요소 이므로 arr[end] - arr[start] 순서로 계산
windowSum += arr[end] - arr[start];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
const result = maxSumSubarray([2, 1, 5, 1, 3, 2], 3);
console.log(result); // 9
위 예시는 슬라이딩 윈도우 기법을 사용하여 배열 내 연속된 k개 요소의 최대 합을 찾는 함수다. 예를들어 초기 배열 [2, 1, 5, 1, 3, 2] 에서 처음 3개 요소의 합은 2 + 1 + 5 = 8 이다. 이후 윈도우를 한 칸씩 이동하면서 k개의 요소를 더해 나간다.
한편 매번 윈도우에 있는 모든 k개 요소를 반복해서 더할 필요없이, 이전 윈도우에서 계산한 값에, 새로 추가할 요소와 제거할 요소를 반영하면 합계를 더 효율적으로 업데이트할 수 있다. 이전 윈도우 계산값 + (추가하는 요소 - 빠지는 요소)
시각적으로 표현해보면 아래와 같다.
슬라이딩 윈도우 기법으로 배열내 연속된 k개 요소의 최대 합을 찾는 과정
프로그래머스 레벨 2 - 할인행사 문제(131127)도 슬라이딩 윈도우 기법을 활용할 수 있다. 주어진 할인 목록(discount)에서 10일 연속 구간에 포함되어 있는 제품/수량과, 구매하고 싶은 제품/수량이 정확히 일치하는 경우의 총 개수를 구하는 문제다.
문제를 해결하려면 discount 배열을 0번 인덱스부터 순회하면서, 해당 위치에서 시작하는 10일 구간의 할인 제품/수량이, 구매 제품/수량과 일치하는지 여부를 확인하면 된다.