Sliding Window(슬라이딩 윈도우)

✅Sliding Window (슬라이딩 윈도우) 알고리즘

Sliding Window(슬라이딩 윈도우) 알고리즘은 배열 또는 리스트에서 일정한 크기의 범위를 유지하면서 이동하는 기법입니다. 즉, 고정된 크기(또는 가변 크기)의 윈도우를 활용하여 데이터를 효율적으로 탐색하는 방법입니다.

활용 예시:

• 배열, 문자열의 특정 범위 내 최대/최소값 찾기
• 연속된 부분 배열의 합 계산 (최대 또는 최소 합 등)
• 문자열 내 패턴 찾기 (애너그램, 부분 문자열 검색 등)

---

1️⃣ Sliding Window 기법이 필요한 이유

브루트 포스(완전 탐색) 를 사용하면 모든 경우를 검사해야 하므로 시간 복잡도가 높아 비효율적입니다.
하지만 Sliding Window를 사용하면 불필요한 계산을 줄이고 효율적으로 문제를 해결할 수 있습니다.

 

✔ Sliding Window의 핵심 아이디어

1. 처음 윈도우에서 값을 계산
2. 다음 윈도우로 이동하면서 기존 윈도우 값 일부를 제거하고, 새 값을 추가
3. 불필요한 중복 계산을 줄여 시간 복잡도를 줄임

---

2️⃣ 고정 크기(Fixed Size) Sliding Window 예제

🔹 문제: 길이 N의 배열에서 크기 K인 부분 배열의 최대 합을 구하라.

✔ Brute Force (완전 탐색, O(NK))

def max_subarray_sum(arr, K):
    max_sum = float('-inf')
    for i in range(len(arr) - K + 1):
        max_sum = max(max_sum, sum(arr[i:i+K]))
    return max_sum

arr = [2, 1, 5, 1, 3, 2]
K = 3
print(max_subarray_sum(arr, K))  # 9

✔ Sliding Window (O(N))

def max_subarray_sum(arr, K):
    window_sum = sum(arr[:K])  # 첫 번째 윈도우 합
    max_sum = window_sum
    
    for i in range(len(arr) - K):
        window_sum = window_sum - arr[i] + arr[i + K]  # 첫 번째 값 제거, 다음 값 추가
        max_sum = max(max_sum, window_sum)
    
    return max_sum

arr = [2, 1, 5, 1, 3, 2]
K = 3
print(max_subarray_sum(arr, K))  # 9

📌 완전 탐색은 모든 부분 배열을 직접 계산하지만, Sliding Window는 한 칸씩 이동하며 계산을 최적화!

---

3️⃣ 가변 크기(Variable Size) Sliding Window 예제

🔹 문제: 배열에서 연속된 부분 배열의 합이 S 이상이 되는 가장 짧은 길이를 구하라.

✔ Sliding Window (O(N))

def min_subarray_length(arr, S):
    left = 0
    window_sum = 0
    min_length = float('inf')
    
    for right in range(len(arr)):
        window_sum += arr[right]  # 오른쪽 값 추가
        
        while window_sum >= S:  # 조건을 만족하면 왼쪽 값 제거
            min_length = min(min_length, right - left + 1)
            window_sum -= arr[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

arr = [2, 3, 1, 2, 4, 3]
S = 7
print(min_subarray_length(arr, S))  # 2 (4+3)

 

✔ 윈도우 크기를 가변적으로 조정하면서 최소 길이 조건을 만족하는 부분 배열을 찾음.

---

4️⃣ Sliding Window 정리

유형	설명	시간 복잡도
고정 크기	윈도우 크기가 고정됨	O(N)
가변 크기	윈도우 크기가 조건에 따라 조정됨	O(N)

 

📌 Sliding Window 기법을 활용하면 중복 계산을 피할 수 있어 효율적으로 문제 해결 가능!