Sliding Window(슬라이딩 윈도우)

Sliding Window(슬라이딩 윈도우)

• 배열이나 리스트에서 일정한 크기의 윈도우(구간)을 유지하면서, 매번 전체를 계산하지 않고 일부만 갱신하는 방식

필요 이유

• 배열에서 연속된 부분을 탐색하는 경우, 모든 경우에 대해 직접 탐색(완전탐색, Brute Force)는 비효율적이기 때문
• 불필요한 연산을 줄이기 위함

유형

1. 고정 크기(Fixed Size) 슬라이딩 윈도우

• 윈도우 크기 K가 일정한 경우 : 연속된 K개의 합 구하기

2. 가변 크기(Variable Size) 슬라이딩 윈도우

• 특정 조건을 만족할 때까지 윈도우 크기를 조절하는 방식 : 연속된 숫자의 합이 특정 값 이하가 될 때 가장 긴 길이 찾기

Brute Force vs Sliding Window

Brute Force

• 길이가 N인 배열에서 크기가 K인 연속된 부분 배열의 합을 구하는 문제
• 아래 코드처럼 작성하면 O(N*K)의 시간 복잡도를 가지므로 데이터가 커지면 매우 비효율적임

package Sliding_Window;

public class BruteForce {
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 6, 4, 8, 9};
        int K = 3; //범위 안에 들어갈 개수
        int maxSum = 0;

        for (int i = 0; i <= arr.length - K; i++) {
            //i는 시작점
            System.out.println("i : " + i);
            System.out.println();
            int sum = 0;
            for (int j = i; j < K + i; j++) {
                System.out.println("j : " + j);
                sum += arr[j];
            }
            System.out.println();
            System.out.println();

            maxSum = Math.max(maxSum, sum);
            System.out.println("최대 값 : " + maxSum);
        }
    }
}

i : 0

j : 0
j : 1
j : 2


최대 값 : 6
i : 1

j : 1
j : 2
j : 3


최대 값 : 11
i : 2

j : 2
j : 3
j : 4


최대 값 : 12
i : 3

j : 3
j : 4
j : 5


최대 값 : 18
i : 4

j : 4
j : 5
j : 6


최대 값 : 21

Sliding Window

• 앞에서 값을 빼고 뒤에서 값을 추가하는 방식으로 불필요한 연산을 줄여 O(N)으로 최적화하는 기법

1. 초기 구간을 계산
2. 윈도우를 이동하면서 업데이트(왼쪽 값을 제거하고 오른쪽 값 추가)

package Sliding_Window;

public class SlidingWindow {
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 6, 4, 8, 9};
        int K = 3;
        int maxSum = 0;

        //1. 첫 번째 윈도우의 값을 계산
        int sum = 0;
        for (int i = 0; i < K; i++) {
            sum += arr[i];
        }
        maxSum = sum;

        //2. 윈도우를 한 칸씩 이동하면서 업데이트
        for (int i = K; i < arr.length; i++) {//위의 for문에서 i가 2까지 돌았으므로 3부터 시작. i가 배열의 끝까지 돌아야 함
            System.out.println("i : " + i);
            int left = arr[i - K]; //슬라이딩 윈도우에서의 가장 왼쪽 값(빼야 할 값)은 배열의 0번방이기 때문에 K를 빼 주어야 함
            System.out.println("왼쪽 값 : " + left);
            int right = arr[i];
            System.out.println("오른쪽 값 : " + right);
            sum = sum - left + right;
            maxSum = Math.max(sum, maxSum);
        }
        System.out.println("최대 값 : " + maxSum);
    }
}

i : 3
왼쪽 값 : 1
오른쪽 값 : 6
i : 4
왼쪽 값 : 3
오른쪽 값 : 4
i : 5
왼쪽 값 : 2
오른쪽 값 : 8
i : 6
왼쪽 값 : 6
오른쪽 값 : 9
최대 값 : 21

예제

문제 : 0을 한 개만 바꿀 수 있을 때, 가장 긴 1의 연속 부분 찾기

package Sliding_Window;

public class VariableSlidingWindow {
    public static void main(String[] args) {
        int[] arr = {1, 1, 0, 1, 1, 0, 1, 1, 1};
        int left = 0; //시작값
        int right = 0; //끝값
        int maxLength = 0;
        int zeroCount = 0;

        while (right < arr.length) { //무조건 끝 값은 한 칸씩 증가시킴
            if (arr[right] == 0) { //0이 나오면 카운트 증가
                zeroCount++;
            }
            while (zeroCount > 1) { //윈도우에 0이 2개 이상이면 다음 단계로 넘어가야 함 -> 0을 한개만 1로 바꿀 수 있기 때문
                if (arr[left] == 0) { //빠지는 값이 0이면 감소
                    zeroCount--;
                }
                left++; //right값은 한 칸씩 계속 증가되므로 left를 이용해서 범위를 축소시켜야 함
            }
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        }
        System.out.println("최대 길이 : " + maxLength);
    }
}

i : 3
왼쪽 값 : 1
오른쪽 값 : 6
i : 4
왼쪽 값 : 3
오른쪽 값 : 4
i : 5
왼쪽 값 : 2
오른쪽 값 : 8
i : 6
왼쪽 값 : 6
오른쪽 값 : 9
최대 값 : 21