Algorithm - Sliding Window

Sliding Window

• Sliding Window 는 배열이나 리스트 속에서 연속된 수의 합 중, 가장 큰 합을 구한다거나 할 때 좋다.

• A B C D E 중, 3 연속의 합을 비교한다고 가정하면,

• A B C 를 처음에 더하고, 다음에는 D 와 A의 차이만큼 합치고, 그 다음에는 E 와 B의 차이를 합치는 방식이다.

• 즉, 창문을 밀 듯 구하는 알고리즘이라 하여 슬라이드 윈도우이다.

• 다음은 K일 동안 연속된 매출액의 합 중 가장 큰 매출액 합을 구하는 문제이다.

   public static int slidingWindowAlgorithm(int n, int m, int[] arr) {
       int answer = Integer.MIN_VALUE;
       int sum = 0;
  
       for ( int i=0; i<m; i++ ) sum += arr[i];
       answer = sum;
  
       for ( int i=m; i<n; i++ ) {
           sum += (arr[i]-arr[i-m]);
           answer = Math.max(answer, sum);
       }
  
       return answer;
   }
  

• 연속된 값의 합을 구하는 문제에서, 연속되는 갯수가 일정하다면 ( ex. 연속된 3개의 합 ) Slide Window 알고리즘을 사용하자.