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

슬라이딩 윈도우 알고리즘

- 배열이나 리스트 요소의 일정 범위 값을 비교할 때 사용하면 유용한 알고리즘

- 투포인터 사용. 투포인터와의 차이는 구간의 넓이가 항상 동일하다는 것

- 핵심: 공통 요소를 재사용하는 것

- start와 end를 사용하고 end가 이동하면서 조건을 벗어나면 start가 이동하는 구조

 

문제 예시)

1. 정수로 이루어진 배열 [ 2,4,7,10,8,4,5,6,7,1]에서 길이가 3인 서브배열의 합계가 가장 큰 서브배열은?

arr는 주어진 배열, k는 길이

int solution(vector<int> arr, int k){
	int start = 0, end = 0;
    int maxSum = 0;
    int sum = 0;
    
    while(end<arr.size()){
    	sum += arr[end++];
        
        if(end-start >= k){
        	maxSum = max(maxSum, sum);
            sum -= arr[start];
            start++;
        }
    }
    return maxSum;
}

 

2. leetcode - max consecutive ones 3

 

eazymean.tistory.com/41

[leetcode 1004] Max Consecutive Ones III

 

 

참고:

blog.fakecoding.com/archives/algorithm-slidingwindow/

m.blog.naver.com/kks227/220795165570