슬라이딩 윈도우

슬라이딩 윈도우(Sliding Window)는 일정한 길이의 범위를 이동하면서 조건에 맞는 값을 찾는 알고리즘 기법입니다. 이 알고리즘은 배열이나 리스트와 같은 연속된 데이터 구조에서 매우 유용하게 사용됩니다.

슬라이딩 윈도우의 작동 방식은 다음과 같습니다:

일정한 크기의 윈도우를 설정하고, 윈도우 내의 값을 기반으로 원하는 조건을 계산합니다.
윈도우를 한 칸씩 이동하면서 새로운 값이 추가되고 이전 값이 제거됩니다.
이렇게 윈도우를 이동하면서 공통된 부분은 유지하고 처음과 끝 원소만 갱신하면서 원하는 조건을 계산하게 됩니다.
필요한 경우 최종 결과를 반환하거나 문제에 맞게 활용합니다.

슬라이딩 윈도우를 활용하면 연속적인 데이터 구조에서 원하는 결과를 빠르게 도출할 수 있으며, 시간 복잡도를 최소화하여 다양한 문제를 효과적으로 해결할 수 있습니다.(O(N))

java

    public static int maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int maxSum = Integer.MIN_VALUE;
        int windowSum = 0;

        // 초기 윈도우의 합 구하기
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }

        // 초기 윈도우의 합을 최대값으로 설정
        maxSum = Math.max(maxSum, windowSum);

        // 슬라이딩 윈도우 이동
        for (int i = k; i < n; i++) {
            windowSum = windowSum - nums[i - k] + nums[i];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }