슬라이딩 윈도우(Sliding Window) 완전 정복! 🪟

슬라이딩 윈도우는 배열이나 문자열에서 일정 크기의 범위를 유지하면서 이동하며 문제를 해결하는 알고리즘입니다.
특히 연속된 데이터의 부분집합을 다룰 때 유용하죠!

핵심 개념 🎯

마치 기차의 창문처럼, 고정된 크기의 '창문'을 한 칸씩 밀면서 이동합니다.

[1 2 3] 4 5 6 7  // 첫 번째 창문 (1,2,3)
1 [2 3 4] 5 6 7  // 두 번째 창문 (2,3,4)
1 2 [3 4 5] 6 7  // 세 번째 창문 (3,4,5)
...

주요 사용 사례 💡

1. 고정 크기 윈도우

   • K 크기의 연속 부분 배열의 최대/최소값
   • K 길이의 연속된 문자열 패턴

2. 가변 크기 윈도우

   • 특정 조건을 만족하는 최소/최대 길이의 부분 배열
   • 합이 특정 값이 되는 연속된 구간

구현 방법 ⚙️

1. 고정 크기 윈도우 예제

// K 크기의 연속 부분 배열의 최대 합 찾기
public int maxSumFixedWindow(int[] arr, int k) {
    // 1. 첫 번째 윈도우의 합 계산
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    int maxSum = windowSum;

    // 2. 윈도우 슬라이딩
    for (int i = k; i < arr.length; i++) {
        // 이전 윈도우의 첫 번째 요소는 빼고
        // 새로운 요소는 더하기
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

2. 가변 크기 윈도우 예제

// 합이 target이 되는 최소 길이의 연속 부분 배열 찾기
public int minSubArrayLen(int target, int[] nums) {
    int minLength = Integer.MAX_VALUE;
    int windowSum = 0;
    int start = 0;

    for (int end = 0; end < nums.length; end++) {
        windowSum += nums[end];

        // 합이 target보다 크거나 같으면
        // 시작 포인터를 이동하며 최소 길이 찾기
        while (windowSum >= target) {
            minLength = Math.min(minLength, end - start + 1);
            windowSum -= nums[start];
            start++;
        }
    }

    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

실전 문제 예시 📝

1. 최대 평균값 부분 배열

// K 크기 연속 부분 배열의 최대 평균값 찾기
public double findMaxAverage(int[] nums, int k) {
    double sum = 0;
    // 첫 윈도우의 합
    for (int i = 0; i < k; i++) {
        sum += nums[i];
    }

    double maxSum = sum;

    // 윈도우 이동
    for (int i = k; i < nums.length; i++) {
        sum = sum - nums[i - k] + nums[i];
        maxSum = Math.max(maxSum, sum);
    }

    return maxSum / k;
}

2. 모든 아나그램 찾기

// 문자열 p의 아나그램이 문자열 s에 있는 모든 위치 찾기
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s == null || p == null || s.length() < p.length()) 
        return result;

    // 문자 출현 횟수를 저장할 배열
    int[] chars = new int[26];

    // p의 문자 횟수 계산
    for (char c : p.toCharArray()) {
        chars[c - 'a']++;
    }

    // 윈도우의 시작과 끝
    int start = 0;
    int end = 0;
    int count = p.length();

    while (end < s.length()) {
        // 끝 포인터 이동
        if (chars[s.charAt(end) - 'a'] >= 1) {
            count--;
        }
        chars[s.charAt(end) - 'a']--;
        end++;

        // 아나그램 찾음
        if (count == 0) {
            result.add(start);
        }

        // 윈도우 크기가 p의 길이와 같아지면
        // 시작 포인터 이동
        if (end - start == p.length()) {
            if (chars[s.charAt(start) - 'a'] >= 0) {
                count++;
            }
            chars[s.charAt(start) - 'a']++;
            start++;
        }
    }

    return result;
}

시간 복잡도 최적화 💫

• 일반적인 시간 복잡도: O(n)
• 공간 복잡도: O(1) 또는 O(k) (k는 윈도우 크기)

실전 팁 🌟

1. 초기 윈도우 설정

   • 첫 번째 윈도우의 계산을 확실히 하기

2. 경계 조건 체크

   • 배열 길이 < 윈도우 크기인 경우 처리

3. 윈도우 이동 시 최적화

   • 이전 계산 결과를 재활용하기

마치며 🎁

슬라이딩 윈도우는 브루트 포스로 해결하면 O(n²)이 걸리는 문제를
O(n)으로 해결할 수 있게 해주는 강력한 기법입니다.
특히 연속된 구간을 다루는 문제에서는 반드시 고려해봐야 할 알고리즘이죠!

---

실전 문제를 더 풀어보고 싶으신가요? 댓글로 남겨주세요! 😊

#알고리즘 #슬라이딩윈도우 #코딩테스트 #Java #알고리즘패턴