🔍슬라이딩 윈도우 (Sliding Window)

슬라이딩 윈도우 알고리즘은 배열이나 문자열과 같은 선형 자료구조에서
일정 크기의 창(window)을 만들고 이동시키면서 원하는 결과를 찾는 알고리즘입니다

📌 슬라이딩 윈도우의 원리

슬라이딩 윈도우는 창(window)을 이용해 다음과 같은 방식으로 작동합니다

1. 먼저 창의 크기를 정한 후, 시작 지점에서부터 창 크기만큼 요소를 포함시킵니다

2. 창을 오른쪽으로 한 칸씩 이동시키면서 창 안의 요소를 기준으로 연산을 수행합니다
   

3. 이동할 때 창에서 빠지는 요소와 새로 들어오는 요소만을 이용하여 이전에 계산한 값을 갱신합니다

📌 슬라이딩 윈도우의 활용

• 배열에서 일정 길이의 연속된 부분 배열의 최대 합 또는 최소 합을 구할 때
• 문자열에서 특정 조건을 만족하는 부분 문자열을 찾을 때
• 데이터 스트림에서 최근 n개 요소의 평균이나 합을 빠르게 계산할 때

📌 슬라이딩 윈도우의 장점

• 중복 계산을 피함으로써 시간 복잡도를 줄일 수 있습니다
  - ex) O(n^2) -> O(n)으로 개선가능
• 고정된 크기의 윈도우를 사용하며 데이터를 처리하기 때문에 메모리 사용량이 일정하게 유지됩니다

📌 슬라이딩 윈도우의 단점

• 적절한 윈도우 크기를 설정하지 않으면 알고리즘의 성능이 저하됩니다

🚀 슬라이딩 윈도우가 적용된 문제

LeetCode 2025-03-09 데일리 문제는 대표적으로 슬라이딩 윈도우 알고리즘을 통해 해결할 수 있습니다

colors 배열의 길이가 10^5 이므로 브루트포스로는 해결할 수 없기 때문에
O(n)의 시간 복잡도로 해결할 수 있는 슬라이딩 윈도우 알고리즘을 적용해야 합니다

        int left = 0;
        int right = 1;
        while(right < len){
            if(arr[right] == arr[right-1]){
                left = right;
                right++;
                continue;
            }
            right++;
            if(right - left < k){
                continue;
            }
            ans++;
            left++;
        }

이처럼 window 크기를 초반에 고정시키지 않고,
탐색 도중 윈도우 크기에 도달하는 순간 고정하는 방법으로도 응용할 수 있습니다

✍️결론

슬라이딩 윈도우는 연속된 데이터에서 최적의 결과를 찾는 데 매우 유용한 알고리즘입니다
이를 통해 시간복잡도를 줄이고, 원하는 결과를 빠르게 찾을 수 있습니다

✅참고

• 슬라이딩 윈도우 개념 참고