이번에는 Sliding Window에 대해서 정리해보려고한다.

Sliding Window?

• 슬라이딩 윈도우는 읽는 길이를 유지하면서 이동하며 읽어내는 알고리즘이다.
• 왼쪽 값과 오른쪽 값을 설정해두고 각 값을 변화시키며 읽는 길이를 유지하면 된다.
• 예를 들어 살펴보자. (1, 2, 7, 4, 1 / 연속된 2개의 수의 합이 가장 클 때를 구하시오.)
  • 0회
    • sum = 10 (1 + 2 + 7) / answer = 10
    • answer는 초기 값으로 설정 된 10을 가지고 시작한다.
  • 1회
    • sum = 13 (2 + 7 + 4) / answer = 13
    • arr[i-len]의 값인 1을 빼고, arr[i]의 값인 4륻 더해준다.
  • 2회
    • sum = 12 (7 + 4 + 1) / answer = 13
    • arr[i-len]의 값인 2을 빼고, arr[i]의 값인 1을 더해준다.
  • 출력
    • answer = 13

코드

• 아래 코드를 참고하길 바란다.

  public class SlidingWindow {
      public static void main(String[] args) {
          int[] arr = new int[]{1, 2, 7, 4, 1};
          int len = 3;
          int answer, sum = 0;
  
          for(int i = 0; i < len; i++){ // sum의 초기 값 설정
              sum += arr[i];
          }
          answer = sum;
  
          for(int i = len; i < arr.length; i++){
              sum += arr[i] - arr[i-len]; // arr[i]는 window의 다음 숫자, arr[i-len]은 window의 첫번째 숫자
              if(sum > answer) {
                  answer = sum;
              }
          }
  
          System.out.println(answer);
      }
  }
  

시간복잡도 & 첨언

• 왼쪽 값과 오른쪽 값을 설정해두고 각 값을 증가시키며 살펴보는 방법을 이용한다면 아래와 같은 문제가 발생한다.
  • 위는 간단한 예시이지만, 만약 window의 크기가 커지게 된다면 시작 값부터 끝 값까지의 총 합을 계속 구해만 할 것이다.
  • 그렇게 된다면 O(n^2)의 시간 복잡도가 만들어지므로, 맨 왼쪽 값을 빼주고 맨 오른쪽 값을 더하면서 비교함으로써 시간복잡도를 O(n)으로 완화시킬 수 있다.