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

슬라이딩 윈도우 방법

슬라이딩 윈도우 방법은 여러 번의 반복을 하나의 반복으로 줄이는 것을 목적으로 하는 방법입니다. 예를 들어 자전거 체인에 기름칠을 할 때 체인 하나하나에 기름을 바르는 것이 아니라 천을 기름에 적신 후 천을 대고 체인을 돌리면 쉽게 바를 수 있습니다.

사용 예시

어떤 리스트 `arr`이 주어 젔을 때 연속된 3개 요소의 최대 합을 구하는 문제가 있다고 가정하겠습니다.
입력: `arr = [3, 5, 7, 5, 3, 2]`
출력: 17
풀이:
3 + 5 + 7 = 15
5 + 7 + 5 = 17
7 + 5 + 3 = 15
…
이므로 17이 최대 합입니다.

만약 이를 일반적으로 푼다면 다음과 같이 풀 수 있을 것입니다.

arr = [3, 5, 7, 5, 3, 2]

max_sum = -inf
for i in range(len(arr) - 3 + 1):
    curr_sum = 0
    for j in range(3):
        curr_sum += arr[i + j]
    max_sum = max(max_sum, curr_sum)

print(max_sum)
# 17

이 경우 2개의 반복문을 포함하고 있기 때문에 시간 복잡성은 `O(3n)`입니다.

하지만 슬라이딩 윈도우 방법을 적용한다면 어떨까요?

arr = [3, 5, 7, 5, 3, 2]

max_sum = window_sum = sum(arr[:3])
for i in range(len(arr) - 3):
    window_sum += -arr[i] + arr[i+3]
    max_sum = max(max_sum, window_sum)

print(max_sum)
# 17

슬라이딩 윈도우 방법을 이용한다면 반복문을 1개만 이용하여 문제를 풀 수 있습니다.

그렇다면 어떻게 반복문 개수를 줄일 수 있었을까요? 아래 코드에서 우리는 새로운 반복문을 제작하는 것이 아니라 양 옆의 요소를 더하고 빼는 방법을 이용했습니다. 이러한 방법을 마치 창문을 밀고 가는 것 같다고 해서 슬라이딩 윈도우(Sliding Window) 방법이라고 합니다.

특징

슬라이딩 윈도우 방법을 이용하기 위해서는 이름과 같이 창이 존재해야 합니다. 이 창은 모든 반복에 걸쳐 고정된 크기를 갖고 있어야 합니다.

슬라이드 윈도우 방법 적용

1. 필요한 고정된 창 크기를 찾아야 합니다
2. 1번째 창 결과를 계산해야 합니다.
3. 반복문을 이용해 창문을 1칸 밀고 창 별로 계속 계산합니다.

참고

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