[알고리즘] 슬라이딩 윈도우

슬라이딩 윈도우는 어떠한 배열에서 일정 범위의 값을 비교할 때 유용하게 사용될 수 있는 방법이다. 투 포인터와 비슷하다고 생각할 수 있지만 투 포인터는 정렬된 배열 내에서 가변적인 범위를 탐색하는 반면 슬라이딩 윈도우는 정렬의 유무와 상관없이 고정적인 범위를 탐색한다는 것에 차이가 있다.

---

개념

슬라이딩 윈도우는 어떠한 배열에서 고정된 크기의 범위를 탐색할 때 유용하게 사용된다. 아래의 그림과 같은 배열을 예시로 확인해보자. 아래의 배열 중에서 연속된 세개의 수를 선택하여 그 합이 최대가 되는 구간이 어디인지 구하려고 한다.

이를 위해 아래의 그림처럼 처음부터 세개의 수를 선택하여 합을 구할 수 있을 것이다. 순서대로 (3 - 1 + 8)을 계산하고 (-1 + 8 - 2)를 계산하면서 진행하는데 (-1 + 8) 부분은 중복으로 계산이 진행된다. 

 

이미 계산된 (-1 + 8)을 사용하면 좋을 것 같다는 생각이 든다. 이를 슬라이딩 윈도우 기법을 적용해서 다시 확인해보자.

먼저 (3 - 1 + 8)을 계산한다. 그리고 가장 왼쪽에 있는 3을 빼주고 다음 차례인 -2를 더해준다면 (-1 + 8)을 두 번 계산하는 것을 피할 수 있게된다.

 

구현

위의 예시를 python으로 구현해보자.

- 먼저 window에 0번 인덱스부터 2번 인덱스까지의 합을 저장한다.

- 이제 3번 인덱스부터 탐색을  진행하고

- window에 현재 인덱스를 더하고 현재 인덱스의 - 3을 한 인덱스를 빼면서 가장 마지막에 계산한 숫자를 빼준다.

- 계산 후에 최댓값 비교를 진행한다.

numbers = [3, -1, 8, -2, 0, 9, -3]
n = len(numbers)
k = 3
window = sum(numbers[:k])
answer = window
for i in range(3, n):
    window += numbers[i] - numbers[i - k]
    answer = max(answer, window)

print(answer)

---

정리

• 슬라이딩 윈도우는 고정적인 범위를 탐색할 때 유용하다.
• 중복으로 연산을 제거하면서 효율을 높일 수 있다.