[python]슬라이딩 윈도우

슬라이딩 윈도우

만약 배열을 순차적으로 순회하는 상황에서 일정한 간격을 통해 배열을 순회해야 한다면 투 포인터를 이용할 수도 있지만, 슬라이딩 윈도우를 이용하여 순회할 수 있습니다.

슬라이딩 윈도우는 배열의 간격만큼의 합을 구한 후, 가장 왼쪽 인덱스의 원소만큼 빼고, 새롭게 추가되는 인덱스의 원소의 값을 더하면서 일정한 간격을 유지하게 됩니다.

아래와 같은 배열이 있다고 하겠습니다.

이 배열에서 연속하는 3개의 원소의 합을 유지하며 배열을 순회하기 위하여 투 포인터를 이용한다면 아래와 같이 순회할 것입니다.

이렇게 첫번째 구간에서 부터 순서대로 좌 우 포인터를 1씩 증가시키게 됩니다.

하지만 슬라이딩 윈도우는 이렇게 투 포인터에서 일정한 간격인 경우에서의 구간합을 통해 간격을 유지하게 됩니다.

이를 위해서는 배열에서의 초기간격만큼의 구간합을 먼저 구해야 합니다.

3만큼의 간격이므로 초기 3개의 원소를 합쳐서 43을 만듭니다. 이제 이 구간합을 갱신해나가며 간격을 유지하게 됩니다. 그다음 구간에서는 10이 빠지고 6이 추가됩니다. 구간합에서 10을 뺀 후 6을 더해주면 간격을 유지하면서 구간합을 갱신할 수 있습니다.

이렇게 말이죠. 이를 코드로 변환하면 아래와 같이 작성할 수 있습니다.

x = 3
arr = [10, 2, 31, 6, 2, 11, 4, 21]
sum = 0 # 초기 구간합 43
for i in range(x):
    sum += arr[i]
for i in range(x, len(arr)):
    sum += arr[i] - arr[i - x]
    print(sum) # 합계 출력

이렇게 슬라이딩 윈도우에 대한 개념을 마칩니다.