Sliding Window Technique

Sliding window Techique이란?

 슬라이딩 윈도우 테크닉은 두개의 사각형을 생각하면 되는데

 하나는 Array, Linked List, Buffer등의 연속적인 데이터를 저장하는 컨테이너이고

 나머지 하나는 저 컨테이너를 훑는 사각형을 생각하면 된다. 

 

 

 

 

Sliding Window Technique의 종류

• '고정된' 사이즈의 윈도우를 가진 슬라이딩 테크닉 기법
• '가변적인' 사이즈의 윈도우를 가진 슬라이딩 테크닉 기법

 

 

 

 

장점

반복적인 요소를 사용하는 문제를 Brute Force로 해결하려 할 때 불필요한 중복이 많이 발생하는데 슬라이딩 윈도우 기법을 사용해 이러한 중복을 줄일 수 있다.

 

 

 

 

사용처

연속적으로 주어진 요소들의 값들(Strings, Array, Linked list등)을 계산해야 할 때 사용할 수 있다.

• Minimum of the value
• Max of the value
• Longest substring of the string
• Shortest substring of the string

 

 

 

---

 

Fixed size sliding window technique

아래와 같이 고정된 사이즈의 윈도우가 컨테이너(String, Array, Linked List)등을 훑으며 최적의 값을 찾는 방식이다.

 

 

 

Example Question

 input) {4, 2, 1, 7, 8, 1, 2, 8, 1, 8}

 subArray의 크기가 3일 때 가장 큰 subArray의 합을 구하시오

public class MaxSumSubArray {
    public static int findMaxSumSubArray(int[] arr, int k) {
        int maxValue = Integer.MIN_VALUE;
        int currentRunningSum = 0;
 
        for(int i = 0; i != arr.length; i++) {
            currentRunningSum += arr[i];
 
 
            if(i >= k - 1) {
                maxValue = Math.max(currentRunningSum, maxValue);
                currentRunningSum -= arr[i - (k-1)];
            }
        }
        return maxValue;
    }
 
    public static void main(String[] args) {
        System.out.println(findMaxSumSubArray(new int[]{4, 2, 1, 7, 8, 1, 2, 8, 1, 0}, 3));
    }
}
 

 

 

 

 

 

 

Dynamic size sliding window technique

가변적인 윈도우의 크기를 가져서 마치 애벌레가 기어가듯이 컨테이너의 끝에 도달할때까지 컨테이너를 훑는 방식이다.

 

 

 

 

 

Example Question

 input) {4, 2, 2, 7, 8, 1, 2, 8, 10}

 합이 8이상인 subArray 중에서 길이가 가장 짧은 subArray의 길이를 구하시오

public class SmallestSubarrayGivenSum {
    public static int smallestSubarray(int targetSum, int[] arr) {
        int minWindowSize = Integer.MAX_VALUE;
        int currentWindowSum = 0;
        int windowStart = 0;
        for(int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
            currentWindowSum += arr[windowEnd];
 
            while(currentWindowSum >= targetSum) {
                minWindowSize = Math.min(minWindowSize, windowEnd - windowStart + 1);
                currentWindowSum -= arr[windowStart];
                // 슬라이딩 윈도우를 이동시킨다
                windowStart++;
            }
        }
        return minWindowSize;
    }
 
    public static void main(String[] args) {
        int[] input = new int[]{4, 2, 2, 7, 8, 1, 2, 8, 10};
        int targetSum = 8;
        System.out.println(smallestSubarray(targetSum, input));
    }
}
 

 

 

 

 

 

---

Reference

www.youtube.com/watch?v=MK-NZ4hN7rs

www.geeksforgeeks.org/window-sliding-technique/

Window Sliding Technique - GeeksforGeeks