Window Sliding Technique

알고리즘 기법 중 윈도우 슬라이딩(Window Sliding)에 대해 알아보려고 한다. 

말 그대로 윈도우 슬라이딩은 윈도우를 움직이는 것이다. 즉, k 크기의 윈도우를 먼 쪽으로 움직인다. (물론 윈도우를 움직이는 방식은 문제를 어떤 식으로 정의하는지에 따라 달라질 수 있다.)

한 예를 들어보면,

Array[] = {5, 2, -1, 0, 3}, 윈도우 크기 k = 3

라면, 인덱스 0번 부터 연속되는 3개를 포함하는 윈도우를 오른쪽으로 한 칸씩 움직이게 되며 인덱스 2번이 마지막이 된다. (슬라이딩 윈도우 정의를 위한 단순 예시) 

그러므로 해당 기법을 정리하면 아래와 같이 간단하다.

1. 윈도우 크기를 정한다.

2. 윈도우 크기 만큼 인덱스 0번 부터 마지막 까지 움직이다. (고정된 크기의 윈도우에 항상 값이 포함되어야 한다. 빈값 X)

관련 코드는 아래와 같다.

def maxSum(arr, n, k):         # n must be greater than k      if not n > k:          print("Invalid")          return -1        # Compute sum of first window of size k      max_sum = INT_MIN      window_sum = sum([arr[i] for i in range(k)])         # Compute sums of remaining windows by      # removing first element of previous      # window and adding last element of      # current window.      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

해당 코드는 배열에서 연속되는 k 값 중 가장 큰 값을 찾는 문제에 대한 것이다.

슬라이딩 윈도우는 부분 합으로 배열을 만든 후에 for-loop에서 적용된다.

위에서 설명한 개념과 같이 슬라이딩 윈도우의 마지막은 n-k로 빈 값이 없는 부분 배열이 되어야 한다.

(물론 문제는 각 윈도우에서 부분합 계산을 통해 최대 값을 찾는다.)

이러한 기법의 등장 이유는 위의 코드에서 한 눈에 볼 수 있듯이 시간 복잡도를 줄이기 위함이다.

보통 중첩되는 반복문을 사용하였을 경우 시간 복잡도가 O(n^2)와 같이 늘어 날 수 있는데 슬라이딩 윈도우를 통해 O(n)과 같이 선형 시간으로 줄일 수 있다.

Reference

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