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

• 투포인터는 연속 구간의 길이가 가변적으로 변할 때 O(2*N)으로 풀도록 도와줌.
• 슬라이딩 윈도우는 구간의 크기가 고정일때.
• 둘다 start, end 포인트 사용(슬라이딩 윈도우는 end가 그냥 배열 포인터긴 함.)
• 하지만 둘다 연속적인 값들을 이용해 풀어나가는 한계가 있음.

 

---

 

기존 배열의 구간합 구하는 코드

• 배열 크기에서 구간의 길이k만큼의 모든 배열의 합을 순회하며 계산.

import sys

def max_sub_array(arr, k):
    maxsum = -sys.maxsize - 1
    arraysize = len(arr)

    for i in range(arraysize - k + 1):
        current_sum = 0
        for j in range(i, i + k):
            current_sum += arr[j]

        maxsum = max(maxsum, current_sum)

    return maxsum

if __name__ == '__main__':
    print(max_sub_array([2, 4, 7, 10, 8, 4, 5, 6, 7, 1], 3))

 

 

• 공통된 부분합을 재사용하기 위한 슬라이딩 윈도우

def max_sub_array(arr, k):
    window_sum = 0
    max_sum = 0
    window_start = 0

    for window_end in range(len(arr)):
        window_sum += arr[window_end]  # 슬라이딩 인덱스 범위 요소 합산

        # 슬라이딩 윈도우의 범위가 k 보다 커진 경우
        if window_end >= (k - 1):
            max_sum = max(max_sum, window_sum)
            window_sum -= arr[window_start]  # 슬라이드 윈도우 범위를 벗어난 요소를 합계에서 제거
            window_start += 1  # 슬라이드 윈도우 시작 인덱스 증가

    return max_sum


if __name__ == '__main__':
    print(max_sub_array([2, 4, 7, 10, 8, 4], 3))

• window_start: 슬라이딩 윈도우 시작 인덱스
• window_end: 슬라이딩 윈도우 끝 인덱스
• widdow_sum: 슬라이딩 윈도우 합계

 

 

• 중복되어 더해주는 부분을 없애고 기존의 합에서
• window_end가 k-1보다 커진경우(즉 size가 k가 된 경우) (인덱스 0부터 시작이므로 k-1이 기준.)
• window start(left pointer)을 하나씩 늘려주며 기존 포인터에 있던 배열 요소 만큼만 빼준다.