슬라이딩 윈도우

슬라이딩 윈도우란

• 배열이나 리스트 요소의 일정 범위 값을 비교할 때 유용한 알고리즘
• 정수 배열에서 연속된 정수들의 최대 합을 구할 때 사용된다

예제문제

• 나는 이 문제를 for문에서 i, i+1, i+2 로 찾았는데 슬라이딩 윈도우으로 효율적으로 풀 수 있다(내가 했던 다 찾는 방식은 뭐가 문제인지는 모르겠음)

• 이렇게 k=3일 때, 투 포인터로 정수 요소 3개를 잡는다

• 창문 밀듯 다음 3개를 잡는데, 3개의 합에 빠졌던(12) 요소를 빼고 새로 합류한(20) 요소를 더한다. 그러면서 이전 값과 비교. 이렇게 되면 for문 한 번에 최대 합을 구할 수 있다.

  // 처음 k=3일 때, 윈도우를 잡아준다. 
  
  for(let i = 0; i < k; i++){
    sum += arr[i]
  }
  answer = sum
  
  // 그 후 for문으로 밀고감.
  
  for(let i=k; i<arr.length; i++){
    sum+=(arr[i]-arr[i-k])
    answer = Math.max(sum, answer)
  }

참고: 인프런 강의