[Algorithm]슬라이딩 윈도우(Sliding Window)

✏️ 슬라이딩 윈도우란?

  데이터 구조나 배열을 순차적으로 탐색하는 알고리즘으로 고정 크기의 윈도우를 유지하면서 필요한 작업을 수행하는 기법이다. 이 알고리즘은 배열이나 리스트 등의 순차적 데이터 구조를 다루는 경우에 유용하게 활용된다.

슬라이딩 윈도우의 예시

  [3, -2, -4, -9, 0, 3, 7, 13, 8, -3]라는 배열이 있다고 했을 때, '4'라는 고정된 길이의 부분합을 구한다고 가정한다. 이때 부분의 합들은 (3, -2, -4, -9), (-2, -4, -9, 0) ... 등으로 구할 수 있다.

  여기서 식을 자세히 살펴보면 중복된 부분이 있는데 계산된 합에서 첫번째 인덱스를 빼고, 다음 인덱스를 더하는 식으로 중복되고 있다.

Python 구현

# window 중 가장 큰 합을 구하는 과정

arr = [3, -2, -4, -9, 0, 3, 7, 13, 8, -3] # 예시 array
size = 2 # 고정된 크기
n = len(arr)

window = sum(arr[:size])
answer = window

for i in range(size, n):
	window += arr[i] - arr[i - size]
    answer = max(answer, window)
print(answer)

>>> 21

슬라이딩 윈도우의 장점

1. 이 방법은 고정된 크기의 배열을 다룰 때 유용하게 사용할 수 있다.
2. 일반적으로 $O(n)$의 시간복잡도를 가지며 대부분의 경우에서 효율적이다.