[알고리즘] Sliding Window

Sliding Window 

일정범위(Window 창문)를 움직여서(Sliding) 원하는 값을 추출하는 알고리즘

투포인터 알고리즘과 동일하게 시간복잡도 O(n^2)의 알고리즘을 O(n)으로 바꾸는 알고리즘

창문이 움직이는것 같이 균등한 단위로 움직임

예제 - 연속 최고 매출 찾기

사업자가 자신의 매출을 매일 n일 동안 기록하고 m일 연속 매출의 최댓값을 찾아보자

int n = 10 //10일간의 매출기록

int k = 3 // 연속 일자 3

 

//n=10 길이의 배열을 임의로 생성
int[] arr = {10, 9, 8 ,6, 4, 5, 10, 16, 9, 10};
int k = 3;
int max = Integer.MIN_VALUE;
int sum = 0;
for(int i=0; i<k; i++){
    sum+=arr[i];
}

for(int i=k; i<arr.length; i++){
    sum-=arr[i-k];
    sum+=arr[i];
    max=Math.max(sum,max);
}

최댓값 = 35

위의 그림과 같은 진행을 하며 유리창이 움직이는것같다고 해서 Sliding Window 알고리즘이다~

 

etc.

sliding window와 two pointer 결합해서 나오는 문제가 많은것 같다.

https://github.com/kimdia200/baekjoon_Algorithm/blob/master/src/main/java/inflearn/step03/_05.java

GitHub - kimdia200/baekjoon_Algorithm: 알고리즘 연습