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

'슬라이딩 윈도우' 란 

윈도우(특정 범위)가 있을때 윈도우 내부 요소의 값을 이용하여

문제를 풀이하는 알고리즘입니다.

아래 그림을 참조하면 조금  더 쉽게 이해하실 것입니다.

예를들어 

[1,3,2,6,-1,4,1,8,2] 라는 배열이 있는데, 연속적인 5개의 숫자의 합이 최대의 값을 

구한다고 가정을 해봅시다.

 

[1,3,2,6,-1],4,1,8,2     합 :  11

1,[3,2,6,-1,4],1,8,2     합 :  14

1,3,[2,6,-1,4,1],8,2     합 :  12

1,3,2,[6,-1,4,1,8],2     합 :  18

1,3,2,6,[-1,4,1,8,2]     합 :  14

 

이런 식으로 구해볼 수 있겠죠 ? 

지금은 배열이 짧아서 하나씩 구해볼 수 있지만 배열이 30개, 연속적인 숫자 2개의 합을 구하라하면

일일히 계산해서 할 수 없겠죠.. 그러므로 우린 공통된 패턴을 구해 코드로 구현해야합니다 !

 

개념

첫번째로 1 + 3 + 2 + 6  + (-1) 를 계산을 하고 

두번째로       3 + 2 + 6  + (-1) + 4 를 계산하면되는데 여기서 중복적인 부분이 생기게됩니다.

그럼 중복적인 경우를 코드로 구현한다면 처음 계산된 합에서 맨 앞 인덱스를 빼고, 마지막 인덱스를 더하여

계산하면 되겠죠 ?

 

구현

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

- 이제 5번 인덱스부터 탐색을 진행하고 window에 현재 인덱스를 더하고 현재 인덱스의 -5를 한 인덱스를 빼준다.

- 계산 후 최대값 비교 !

 

numbers = [1,3,2,6,-1,4,1,8,2]
n = len(numbers)
k = 5

window = sum(numbers[:k])
answer = window

for i  in range(5, n):
    window += numbers[i] - numbers[i - k]
    answer = max(answer,window)

print(answer)

결과값

 

정리

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