[2021-09-23] Sliding Window

Sliding Window

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

- 서브 배열의 요소를 순회하다 보면 중복되는 요소들이 존재하고 이 중복된 요소를 재사용하는 방법

- 방법

   1. 윈도우(일정 범위의 요소 ==> k개)의 요소를 원하는 방법으로 처리

   2. 윈도우의 시작부분을 빼고, 윈도우 맨 끝에 새 요소를 추가

 

ex) 2, 4, 7, 10, 8, 4, 6, 5, 7, 1 정수로 이루어진 배열에서 길이가 4인 서브 배열의 합이 가장 큰 서브 배열 구하기

시간복잡도 O(N)