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

Sliding Window 란?

고정된 크기의 윈도우가 이동하면서 윈도우 내의 데이터를 이용해 문제를 풀어가는 알고리즘

배열, 리스트의 요소의 일정 범위의 값을 비교할 때 유용한 알고리즘이다.

 

 

 

 

def maxSum(arr,k):
	n = len(arr) # length of arr
    if n<k: /# 윈도우 사이즈보다 len이 작을때
    	return -1 
        
    window_sum = sum(arr[:k]) # k까지의 합계
    max_sum = window_sum
    
    for i in range(n-k): # 윈도우에서 첫 원소 삭제, 새로운 요소 삽입 
    	window_sum=window_sum - arr[i]+arr[i+k]
        max_sum = max(window_sum, max_sum)
    return max_sum
   
arr = [16, 12, 9, 19, 11, 8]
k=3
print(maxSum(arr,k))

-> 주어진 arr에서 더해서 최대가 되는 값 찾기

 

 

---

참고

https://www.thecrazyprogrammer.com/2017/05/sliding-window-protocol-program-c.html