내일배움캠프 84일차 - 자료구조 & 알고리즘 16주차 : 슬라이딩 윈도우

슬라이드 윈도우 - 구간을 미끄러뜨리며 본다

개념 확인

아래의 숫자가 나열되어 있을 때, 연속된 5칸의 평균이 가장 높은 지점은 어디인가?

3 7 2 8 5 9 4 6

가장 단순한 방법 - 매번 다시 더한다
 : 매 지점마다 그 자리에서 5칸치를 처음부터 다시 더해 평균을 낸다.
 → 1,000칸이면 약 5,000번 연산 (N칸×K번 덧셈)

구간 크기가 커질수록 매 시점 다시 더하는 비용이 그대로 늘어난다는 단점이 있다.

슬라이드 윈도우 방식 - 첫 5칸을 한 칸 뒤로 미끄러뜨리면?

3 7 2 8 5 9 4 6 → 7 2 8 5 9 4 6 3

 : 가운데 세 칸(7,2,8,5)은 그대로, 나가는 값 하나(3)와 들어오는 값 하나(9)만 바뀐다.
 : 이전 5칸의 합을 가지고 있다면 거기서 나가는 값(3)을 빼고, 들어오는 값(9)를 더하면 지금의 5칸 합.
 → 1,000칸이면 약 1,000번 (N칸×1번 덧셈)

구간 크기와 무관하게 "변한 부분만 갱신한다"는 계산 방식이 연산 횟수를 줄인다.

핵심 통찰 - 본질은 "갱신만"

슬라이딩 윈도우의 본질은 "k개의 합을 계산하는 것"이 아니라,
이미 계산한 결과를 "버리지 않고 갱신"만 하는 것이다.