Sliding Window 기법 정리

(참고)

www.geeksforgeeks.org/window-sliding-technique/

Window Sliding Technique - GeeksforGeeks

슬라이딩 윈도우 기법

슬라이딩 윈도우 기법은 시간 복잡도를 줄이기 위해 중첩된 반복문을 어떻게 단일 반복문으로 바꿀 수 있는지 보여줍니다.

 

크기가 N인 정수 배열이 주어지고 k개를 더한 값의 최댓값을 계산하는 문제가 있습니다.

이 문제를 Brute Force Approach로 접근하면 첫 번째 인덱스부터 출발하여 k번째 요소까지 더해야 하는 작업을 k개의 합을 구할 수 있는 모든 경우의 수만큼 반복해야 합니다. 그래서 이 방법은 중첩된 반복문을 필요로 하고, 시간 복잡도는 O(k*N)입니다. (O(k)는 합을 구하는 작업, O(N)은 출발 횟수입니다.)

 

슬라이딩 윈도우 기법은 길이가 n이고 유리창 길이는 k인 버스 창문으로 이해하면 좋습니다. 좀 전에 이야기한 정수 배열을 창문으로, k개 요소의 합은 창문으로 생각할 수 있습니다. 이제, 창문에 힘을 가하면 유리창이 배열 한 칸만큼 웁직인다고 합시다. 그러면 창은 k개의 요소를 덮습니다.

 

배열 arr[] = {5, 2, -1, 0, 3}, k=3, n=5라고 가정해 봅시다.

 

슬라이딩 윈도우 기법을 적용하면,

1. 선형 반복문에서 첫 번째 k요소들의 총합을 계산하고 그 값을 window_sum 변수에 저장합니다.

2. 배열(창문) 끝으로 밀면서 최댓값을 추적합니다.

3. 현재 블럭의 총합을 구하기 위해서는 현재 블럭의 이전 요소는 빼고 마지막 요소를 더하면 됩니다.

 

아래 예시는 어떻게 블럭(유리창)이 배열(창문) 위를 움직이는지 보여줍니다.

1) 첫 번째 단계 (총합: 6)

5 2 -1 0 3

 

2) 두 번째 단계 (총합: 이전 단계(6) - 이전 요소(5) + 마지막 요소(0) = 1)

5 2 -1 0 3

 

3) 세 번째 단계 (총합: 이전 단계(1) - 이전 요소(2) + 마지막 요소(3) = 2)

5 2 -1 0 3

 

- 구현

# O(n) 시간복잡도
import sys 
INT_MIN = -sys.maxsize -1
  
def maxSum(arr, n, k): 
  
    # n은 반드시 k보다 커야 한다
    if not n > k: 
        print("Invalid") 
        return -1
  
    # 크기가 k인 첫번째 윈도우의 합을 계산한다
    max_sum = INT_MIN 
    window_sum = sum(arr[:k]) 
  
    # 위에서 설명한 방법을 반복한다
    for i in range(n-k): 
        window_sum = window_sum - arr[i] + arr[i + k] 
        max_sum = max(window_sum, max_sum) 
  
    return max_sum 

단일 반복문에서의 시간 복잡도는 O(n)으로 매우 효율적입니다. 이 방법은 최대/최소 k-subarray, XOR, 곱, 총합 등에 응용할 수 있습니다.

 

contributed by Kanika Thakral.