슬라이딩 윈도우(Sliding Window) 알고리즘은 배열이나 문자열을 다룰 때, 일정한 크기의 창(window)을 좌우로 움직이며 데이터를 처리하는 알고리즘 기법입니다.
이는 주로 연속된 부분 배열에서의 합, 최대/최소값, 조건 만족 여부 등을 빠르게 구할 때 사용합니다.
이 알고리즘은 성능 향상을 원할 때 아주 유용하게 사용할 수 있고 중복된 계산은 피하면서 연속된 데이터 조각을 효율적으로 처리할 수 있습니다.
Table of Contents
주요 개념
- 윈도우(window)는 배열이나 문자열내에서 연속된 구간(서브 배열)을 말합니다.
- 이 윈도우를 왼쪽에서 오른쪽으로 하나씩 밀면서 이동합니다.
- 이전 결과값을 활용하여 계산량을 줄이는 방식입니다.
예제: 가장 큰 서브 배열의 합 찾기
다음의 문제를 알아보겠습니다:
정수 배열 nums와 정수 k가 주어질 때, 길이가 k인 연속 부분 배열의 최대 합을 구하라
이러한 문제는 다양한 방법으로 풀 수 있습니다.
비효율적인 방식: 브루트포스
function maxSubarraySum(nums, k) {
let max = -Infinity;
for (let i = 0; i <= nums.length - k; i++) {
let sum = 0;
for (let j = 0; j < k; j++) {
sum += nums[i + j];
}
max = Math.max(max, sum);
}
return max;
}위의 예제는 배열의 처음 부터 루프를 돌며 하나 하나 서브 배열의 합을 구하고 있습니다.
이는 단순하고 간단하게 생각할 수 있는 방법이지만 시간 복잡도는 O(n * k)로 효율적이지 않은 방법입니다.
특히 nums 배열이 커질 수록 속도는 더 느려질 것 입니다.
효율적인 방법: 슬라이딩 윈도우
function maxSubarraySum(nums, k) {
if (nums.length < k) return null;
// 초기 윈도우 (맨 앞 k개) 합 계산
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += nums[i];
}
let maxSum = windowSum;
// 윈도우를 한 칸씩 오른쪽으로 이동
for (let i = k; i < nums.length; i++) {
windowSum = windowSum - nums[i - k] + nums[i]; // 앞 빼고 뒤 더함
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}이번 예제에서는 슬라이딩 윈도우 알고리즘을 적용했습니다.
먼저 맨 앞의 윈도우 크기(k)만큼의 계산을 해놓습니다.
그 다음 윈도우를 한칸씩 옮기면서 해당 윈도우 범위에 들지 못한 항목은 빼고 윈도우에 새로 들어온 항목은 더합니다.
이렇게 다음번 윈도우의 계산 결과가 나오면 이전에 계산했던 결과와 비교하여 더 큰 값만 기억하면 문제를 해결할 수 있게됩니다.
시간 복잡도는 o(n)이고, 공간 복잡도는 o(1)입니다.
예시로 확인
구체적인 예를 숫자를 통해 알아보겠습니다:
배열: [2, 1, 5, 1, 3, 2], k = 3
| 윈도우 위치 | 부분 배열 | 합계 |
|---|---|---|
| [2, 1, 5] | 2 + 1 + 5 = 8 | 초기 |
| [1, 5, 1] | 8 – 2 + 1 = 7 | 앞(2) 빼고 뒤(1) 더함 |
| [5, 2, 3] | 7 – 1 + 3 = 9 | |
| [1, 3, 2] | 9 – 5 + 2 = 6 |
이렇게 계산한 최대 합의 최종 결과는 9가 됩니다.
슬라이딩 윈도우 사용 조건
- 고정된 길이의 서브배열이나 서브스트링에서 최대/최소 값을 구할 때
- 연속된 데이터에 대한 조건을 만족하는 구간을 찾을 때
- 효율적인 윈도우 기반 알고리즘이 필요할 때 (예: 투 포인터)
슬라이딩 윈도우 정리
- 개념: 연속된 범위(윈도우)를 이동시키며 값을 계산
- 장점: 중복 계산 제거, 시간복잡도 줄임
- 사용처: 고정 길이의 최대합, 최소합, 조건 만족 구간 찾기 등
- 구현: 초기 합 계산 후, 매 이동마다 앞을 빼고 뒤를 더함