슬라이딩 윈도우 : Sliding Window

 

📌 슬라이딩 윈도우 : Sliding Window

- 배열이나 리스트에서 연속된 부분(구간)을 빠르게 탐색하는 기법

- 불필요한 중복 계산을 줄여 시간 복잡도를 줄이는데 유용

 

 

📌 슬라이딩 윈도우 원리

1️⃣ 초기 구간 (K개의 요소)의 합을 먼저 계산

2️⃣ 윈도우를 한 칸씩 옆으로 이동하면서, 변화하는 값만 반영

- 기존 합에서 빠지는 값은 빼고, 새롭게 추가되는 값은 더하기

- 즉, O(1)의 연산만 수행하여 전체 시간 복잡도를 **O(N)**으로 줄일 수 있음

 

 

✅ 코드 예시

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SlidingWindowExample {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());  // 배열 크기
        int K = Integer.parseInt(st.nextToken());  // 연속된 원소 개수

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 초기 구간 합 구하기
        int sum = 0;
        for (int i = 0; i < K; i++) {
            sum += arr[i];
        }

        int maxSum = sum;

        // 슬라이딩 윈도우 적용
        for (int i = K; i < N; i++) {
            sum = sum - arr[i - K] + arr[i];  // 앞의 값 빼고, 새로운 값 추가
            maxSum = Math.max(maxSum, sum);
        }

        System.out.println(maxSum);
    }
}

 

 

🔥 정리 (슬라이딩 윈도우의 장점)

✔ O(N) 시간 복잡도 → 빠른 연산
✔ 메모리 절약 → 추가 배열 필요 없음
✔ 중복 연산 제거 → 기존 값을 재사용하여 불필요한 계산 방지