[슬라이딩 윈도우] 효율적인 부분 탐색의 핵심

슬라이딩 윈도우(Sliding Window) 

슬라이딩 윈도우(Sliding Window) 기법은 배열이나 문자열에서 연속된 구간(subarray, substring) 을 다룰 때 매우 유용한 최적화 알고리즘입니다.
이 글에서는 슬라이딩 윈도우의 개념, 종류, 구현 방법, 그리고 다양한 언어별(파이썬, C++, 자바, 자바스크립트) 실습 예제까지 제공하여, 초급부터 중급 개발자까지 쉽게 이해하고 응용할 수 있도록 돕겠습니다.

 

---

1.  슬라이딩 윈도우란?

슬라이딩 윈도우는 일정 범위(구간)를 유지하면서, 그 구간을 배열이나 문자열 위에서 한 칸씩 이동(slide) 시키는 기법입니다. 이 방식을 사용하면, 모든 구간을 새로 계산하지 않고, 이전 구간의 정보를 활용해 빠르게 결과를 업데이트할 수 있습니다.

기본 아이디어

1. 초기 윈도우를 설정합니다.
2. 윈도우를 한 칸 이동할 때마다, 새롭게 추가된 값과 제거된 값을 이용해 계산을 빠르게 갱신합니다.

이 과정을 통해 시간 복잡도를 줄여 O(N) 시간에 문제를 해결할 수 있습니다. (브루트 포스 대비 압도적으로 빠름)

슬라이딩 윈도우가 필요한 상황

• 배열 또는 문자열에서 고정 길이의 최대/최소 합 구하기
• 조건을 만족하는 최소/최대 길이의 부분 구간 찾기
• 부분 문자열 문제 해결
• 이동 평균(moving average) 계산

 

---

2.  슬라이딩 윈도우 유형 정리

유형	설명	예시 문제
고정 크기(Fixed-size) 윈도우	윈도우 크기가 항상 일정	최대 합 구하기, 이동 평균
가변 크기(Variable-size) 윈도우	조건에 따라 윈도우 크기가 변함	최소 길이 부분 배열, 가장 긴 부분 문자열

 

---

3.  슬라이딩 윈도우 기본 패턴

a.  고정 크기 윈도우

1. 초기 윈도우 설정 (0부터 k-1까지)
2. 이후 한 칸씩 이동하면서 추가/제거
3. 매 이동마다 결과를 업데이트

b.  가변 크기 윈도우

1. 시작 포인터(start)와 끝 포인터(end) 사용
2. 조건을 만족할 때까지 end를 확장
3. 조건을 초과하면 start를 이동시키며 조정

 

---

4.  주요 언어별 예제 코드

문제 예시 : 길이 k인 부분 배열 중 최대 합을 구하라.

배열 [1, 3, 2, 6, -1, 4, 1, 8, 2]에서 길이 3짜리 부분 배열 중 최대 합은 4+1+8=13입니다.

a.  Python (파이썬)

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]
        max_sum = max(max_sum, window_sum)

    return max_sum

# 사용 예시
arr = [1, 3, 2, 6, -1, 4, 1, 8, 2]
print(max_sum_subarray(arr, 3))  # 출력: 13

b.  C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSumSubarray(const vector<int>& arr, int k) {
    int windowSum = 0, maxSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    maxSum = windowSum;

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

int main() {
    vector<int> arr = {1, 3, 2, 6, -1, 4, 1, 8, 2};
    cout << maxSumSubarray(arr, 3) << endl; // 출력: 13
}

c.  Java (자바)

public class SlidingWindowExample {
    public static int maxSumSubarray(int[] arr, int k) {
        int windowSum = 0, maxSum = 0;

        for (int i = 0; i < k; i++) windowSum += arr[i];
        maxSum = windowSum;

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

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 6, -1, 4, 1, 8, 2};
        System.out.println(maxSumSubarray(arr, 3)); // 출력: 13
    }
}

d.  JavaScript (자바스크립트)

function maxSumSubarray(arr, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    let maxSum = windowSum;

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

    return maxSum;
}

// 사용 예시
const arr = [1, 3, 2, 6, -1, 4, 1, 8, 2];
console.log(maxSumSubarray(arr, 3)); // 출력: 13

 

---

5.  슬라이딩 윈도우 vs 브루트 포스 비교

항목	브루트 포스	슬라이딩 윈도우
시간 복잡도	O(NK)	O(N)
특징	모든 부분 구간을 매번 새로 계산	이전 계산값을 활용하여 빠르게 갱신
장점	단순하고 구현이 쉬움	빠르고 효율적
단점	느림 (N, K가 클 때)	조건 설정이 중요

 

---

6.  마무리

• 슬라이딩 윈도우는 고정 길이 또는 가변 길이 구간을 한 칸씩 이동시키며 효율적으로 탐색하는 기법입니다.
• 브루트 포스보다 훨씬 빠른 O(N) 시간 복잡도를 제공합니다.
• 주로 배열, 문자열 관련 최적화 문제에 활용됩니다.
• 구현 시 윈도우 관리와 경계 조건 체크에 유의해야 합니다.

 

---