슬라이딩 윈도우
배열을 밀고 가면서 연속된 배열 3개의 합이 가장 큰 숫자들의 합을 구하여라.
보통 이런 문제가 나올때 사용하는 알고리즘이라고 한다.
나도 오늘 처음 겪어봤지만 나름 알아봤기 때문에 쉬운 용어들로 정리할것이다.
배열에서 첫 연속된 3개의 합을 sum에 할당하고 다음 인덱스를 더하고,
이전 인덱스를 빼줌으로써 하나씩 밀고 간다는 느낌을 주기 때문에 ,
슬라이딩 윈도우 라고 부르는 것 같다.
이게 그래서 어떻게 동작하는건지? 를 코드로 보면 바로 이해못하겠지만 여러번 보면
이해된다.
for (let i = 0; i < k; i++) {
sum += arr[i];
}
K = 3이고, 거기까지의 합을 sum에 넣어두었다.
참고로 for문이 2개라고 해서 시간복잡도가 O(N^2) 이 아니고
중첩이 아니라 각각 쓰기때문에 O(N) 의 시간복잡도를 가진다.
그런 면에서라도 이 알고리즘은 아주 효율적인거 같다.
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k];
answer = Math.max(answer, sum);
}
i = k(3) 부터 시작해서 arr.length까지 점차 증가하며 포문을 돈다.
sum += arr[i = 3] - arr[3-3] 하면
sum += arr[3] - arr[0]
3번째 인덱스는 기존 구한 배열의 다음 인덱스이고 그 수를 더하고,
arr[0] 번째 값을 빼주는 방식으로
점차 전진하는 느낌인거다.
지금 설명이 이게 최선이다. 이해 못했다면 내 탓이다.
answer = Math.max(answer, sum);
점차 전진하면서 가장 큰 수를 answer에 계속해서 할당해주는 것이다.
진짜 코드도 짧고 이해하고 나면 너무 쉬워서 허무했지만,
다시 쓰라고 하면 자신 없으니 몇번 더 볼 필요가 있다.
앞으로 자주 쓸 것 같다.
