슬라이딩 윈도우

슬라이딩 윈도우(Sliding Window)는 배열 또는 문자열에서 연속적인 요소의 부분집합을 찾는 데 사용되는  알고리즘 기술



알고리즘은 주어진 문제의 해결을 위해 윈도우을 움직이면서 데이터를 처리하고 일부 조건을 충족하는 부분집합을 찾습니다.

 

이는 주로 부분집합의 합, 최대 길이 부분집합, 연속된 부분집합 등을 찾는 데 사용합니다.



1. 처음 시작과 끝으로 지정할 부분 집합의 길이 만큼 탐색한 후 데이터를 초기화 합니다.
2. 끝과 초기 인덱스를 이동하면서 윈도우 내부 데이터를 업데이트를 진행합니다.

 

<출처 : https://dev.to/mwong068/sliding-window-technique-in-ruby-3og4>

아래는 부분 집합의 최대 합을 구하는 문제이다.

public class SlidingWindow {
    public static int findMaxSubarraySum(int[] nums, int k) {
        int maxSum = 0;
        int windowSum = 0;

        // 첫 번째 윈도우의 합 계산
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }

        // 시작 인덱스와 끝 인덱스를 이동하면서 최대 합 찾기
        for (int i = k; i < nums.length; i++) {
            windowSum += nums[i] - nums[i - k]; // 새로운 요소 추가, 이전 요소 제거
            maxSum = Math.max(maxSum, windowSum); // 최대 합 업데이트
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 5, 1, 3, 2};
        int k = 3;
        int maxSum = findMaxSubarraySum(nums, k);
        System.out.println("최대 부분집합의 합: " + maxSum); // (부분집합 [5, 1, 3]의 합)
    }
}