슬라이딩 윈도우 완벽 정리: 개념부터 실전 활용까지

슬라이딩 윈도우 완벽 정리

 

1. 슬라이딩 윈도우란?

슬라이딩 윈도우(Sliding Window)는 배열이나 문자열처럼 연속된 데이터를 처리하는 알고리즘 기법으로, 고정 크기의 윈도우(구간)를 이동시키며 데이터를 효율적으로 계산하거나 처리하는 방식입니다. 이를 통해 반복적인 계산을 줄이고 시간 복잡도를 최적화할 수 있습니다.

 

슬라이딩 윈도우는 대표적인 애드혹(Ad-hoc) 알고리즘 기법입니다. 애드혹 알고리즘에 대한 자세한 설명은 아래 링크에 작성했습니다.

2024.12.26 - [알고리즘] - 애드혹(Ad-hoc) 알고리즘 완벽정리 - 개념, 주의점, 대표기법 총 정리

애드혹(Ad-hoc) 알고리즘 완벽정리 - 개념, 주의점, 대표기법 총 정리

 

---

 

2. 슬라이딩 윈도우의 원리

슬라이딩 윈도우의 핵심은 기존 결과를 재활용하는 것입니다. 윈도우가 한 칸씩 이동할 때, 새로 포함된 데이터와 제외된 데이터를 반영하여 이전 계산을 업데이트합니다.

 

예를 들어, 배열 [1, 3, 5, 7, 9]에서 크기 3의 윈도우로 합을 구한다고 가정하면:

1. 첫 번째 윈도우 [1, 3, 5]의 합: 1 + 3 + 5 = 9
2. 윈도우를 오른쪽으로 이동하여 [3, 5, 7]의 합을 구할 때, 기존 합에서 1을 빼고 7을 더함: 9 - 1 + 7 = 15

이 방식으로 매번 처음부터 합을 계산하지 않고 빠르게 결과를 갱신할 수 있습니다.

 

반응형

---

 

 

3. 시간 복잡도

 

슬라이딩 윈도우를 활용하면, 데이터를 한 번만 순회하면서 결과를 계산할 수 있으므로 시간 복잡도는 O(n)입니다. 이는 각 데이터가 윈도우에 한 번 포함되고, 한 번 제외되기 때문입니다.

---

 

 

4. 슬라이딩 윈도우를 적용하는 대표적인 케이스

(1) 최대/최소 연속 부분합

문제: 주어진 배열에서 연속된 K개의 숫자의 합 중 최대값을 찾으세요.

 

(2) 고유 문자 개수 계산

문제: 문자열에서 고정 크기의 윈도우 내에 포함된 고유 문자의 개수를 구하세요.

 

(3) 특정 조건을 만족하는 구간 찾기

문제: 배열에서 합이 특정 값을 초과하는 최소 구간을 찾으세요.

---

 

 

5. 슬라이딩 윈도우의 장단점

장점

1. 효율성: 반복 계산을 줄여 시간 복잡도를 개선합니다.
2. 단순함: 구현이 비교적 직관적이며 문제 풀이가 쉽습니다.

 

단점

1. 고정된 윈도우 크기: 문제에 따라 유연성이 떨어질 수 있습니다.
2. 적용 범위 제한: 윈도우 크기 변경이 빈번하거나 조건이 복잡한 경우 비효율적일 수 있습니다.

---

 

 

6. 설계 시 주의점

1. 초기 윈도우 설정: 첫 번째 윈도우의 결과를 정확히 계산해야 합니다.
2. 경계 조건 처리: 배열의 시작 또는 끝에서 윈도우가 벗어나는 경우를 처리해야 합니다.
3. 문제 조건 파악: 슬라이딩 윈도우가 문제 해결에 적합한지 확인하세요.

---

 

 

7. 예제 코드

C 언어

#include <stdio.h>

void slidingWindowSum(int arr[], int n, int k) {
    int windowSum = 0;

    // 첫 번째 윈도우의 합 계산
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    printf("Window sum: %d\n", windowSum);

    // 슬라이딩 윈도우 적용
    for (int i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        printf("Window sum: %d\n", windowSum);
    }
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int k = 3;
    slidingWindowSum(arr, 5, k);
    return 0;
}

Java

public class SlidingWindow {
    public static void slidingWindowSum(int[] arr, int k) {
        int windowSum = 0;

        // 첫 번째 윈도우의 합 계산
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        System.out.println("Window sum: " + windowSum);

        // 슬라이딩 윈도우 적용
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k];
            System.out.println("Window sum: " + windowSum);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int k = 3;
        slidingWindowSum(arr, k);
    }
}

Python

def sliding_window_sum(arr, k):
    # 첫 번째 윈도우의 합 계산
    window_sum = sum(arr[:k])
    print(f"Window sum: {window_sum}")

    # 슬라이딩 윈도우 적용
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        print(f"Window sum: {window_sum}")

arr = [1, 3, 5, 7, 9]
k = 3
sliding_window_sum(arr, k)

---

 

 

슬라이딩 윈도우는 배열이나 문자열과 같은 연속된 데이터를 효율적으로 처리할 수 있는 강력한 알고리즘 기법입니다. 다양한 문제에 적용할 수 있으며, 반복 계산을 줄여 시간 복잡도를 최적화할 수 있다는 점에서 매우 유용합니다. 다만, 문제의 조건과 윈도우 크기를 잘 이해하고 적절히 설계해야 효과를 극대화할 수 있습니다.