[알고리즘] 슬라이딩 윈도우 (Sliding Window)

슬라이딩 윈도우란?

슬라이딩 윈도우(Sliding Window)는 배열이나 문자열과 같은 연속적인 데이터에서 특정 크기의 부분 집합을 효율적으로 처리하는 알고리즘 패턴이다. 마치 창문(윈도우)을 한 칸씩 밀어가며 데이터를 살펴보는 것과 같다고 해서 이런 이름이 붙었다.

언제 사용할까?

• 연속된 부분 배열의 최대/최소 합 구하기
• 고유 문자로 이루어진 가장 긴 부분 문자열 찾기
• 특정 조건을 만족하는 부분 배열 찾기

문제 예시: 연속된 부분 배열의 최대 합

정수 배열과 숫자 n이 주어졌을 때, 연속된 n개 요소의 최대 합을 구하는 문제

// 예시: [2, 6, 9, 2, 1, 8, 5, 6, 3], n = 3
// 결과: 19 (8 + 5 + 6)

비효율적인 접근법 (Brute Force)

먼저 직관적이지만 비효율적인 방법을 살펴보자.

function maxSubarraySum_naive(arr, num) {
    // 유효성 검사
    if (num > arr.length) {
        return null;
    }
    
    let max = -Infinity; // 음수 배열을 고려해 -Infinity로 초기화
    
    // 첫 번째 루프: 시작 위치
    for (let i = 0; i <= arr.length - num; i++) {
        let temp = 0;
        
        // 두 번째 루프: num개 요소의 합 계산
        for (let j = 0; j < num; j++) {
            temp += arr[i + j];
        }
        
        // 최대값 갱신
        if (temp > max) {
            max = temp;
        }
        
        console.log(`위치 ${i}에서 ${num}개 요소의 합: ${temp}`);
    }
    
    return max;
}

// 테스트
const arr = [2, 6, 9, 2, 1, 8, 5, 6, 3];
console.log(maxSubarraySum_naive(arr, 3)); // 19

비효율적인 이유

• 시간 복잡도: O(n²) - 중첩된 루프 사용
• 중복 계산: 매번 처음부터 합을 다시 계산
• 예를 들어, [2,6,9]의 합을 구한 후 [6,9,2]의 합을 구할 때 6과 9를 중복으로 계산

효율적인 접근법 (슬라이딩 윈도우)

슬라이딩 윈도우 패턴을 사용하면 중복 계산을 피할 수 있다:

function maxSubarraySum(arr, num) {
    // 유효성 검사
    if (num > arr.length) {
        return null;
    }
    
    let maxSum = 0;
    let tempSum = 0;
    
    // 첫 번째 윈도우의 합 계산
    for (let i = 0; i < num; i++) {
        maxSum += arr[i];
    }
    
    tempSum = maxSum;
    console.log(`초기 윈도우 합: ${maxSum}`);
    
    // 윈도우를 슬라이딩하며 합 갱신
    for (let i = num; i < arr.length; i++) {
        // 핵심: 이전 요소를 빼고 새로운 요소를 더함
        tempSum = tempSum - arr[i - num] + arr[i];
        
        console.log(`윈도우 이동: -${arr[i - num]} +${arr[i]} = ${tempSum}`);
        
        // 최대값 갱신
        maxSum = Math.max(maxSum, tempSum);
    }
    
    return maxSum;
}

// 테스트
const arr = [2, 6, 9, 2, 1, 8, 5, 6, 3];
console.log(`최대 부분 배열 합: ${maxSubarraySum(arr, 3)}`); // 19

슬라이딩 윈도우의 핵심

1. 초기 윈도우 설정: 첫 번째 n개 요소의 합을 계산
2. 윈도우 이동:
   • 왼쪽 끝 요소를 제거 (빼기)
   • 오른쪽에 새로운 요소를 추가 (더하기)
3. 최적값 추적: 각 단계에서 최대값을 갱신

 

핵심 포인트

1. 시간 복잡도 개선: O(n²) → O(n)
2. 중복 계산 제거: 이전 계산 결과를 활용
3. 메모리 효율성: 추가적인 공간 복잡도 최소화
4. 적용 범위: 연속된 부분 집합 문제에 광범위하게 활용 가능