슬라이딩 윈도우란?
슬라이딩 윈도우 기법은 배열 또는 문자열에서 고정 크기의 창(윈도우)를 유지하면서 특정 조건을 충족하는 부분 배열이나 부분 문자열을 찾는 기법이다.
위의 이미지에 [1, 15, 1, 2, 6, 12, 5, 7] 이라는 배열이 있다. 연속적인 4개의 숫자의 합이 가장 큰 값을 구하자고 하자
- 초기에 첫 4개의 숫자로 윈도우를 설정하고 합을 구합니다.
- 윈도우: [1, 15, 1, 2], 합: 19
- 다음으로 윈도우를 한 칸씩 오른쪽으로 이동하면서 새로운 합을 계산합니다.
- 윈도우: [15, 1, 2, 6], 합: 24
- 윈도우: [1, 2, 6, 12], 합: 21
- 윈도우: [2, 6, 12, 5], 합: 25
- 윈도우: [6, 12, 5, 7], 합: 30
슬라이딩 윈도를 사용하면 윈도우를 이동하면서 연속적인 부분 배열의 합을 효율적으로 구할 수 있다.
function maxSubarraySum(arr, num) {
let maxSum = 0;
let tempSum = 0;
// // 우선 첫 번째 합을 maxSum에 저장
for (let i = 0; i < num; i++) {
maxSum += arr[i];
}
tempSum = maxSum;
// arr[0] 빼고 arr[num] 더하면 새로운 window.// 이것을 반복
for (let i = num; i < arr.length; i++) {
tempSum = tempSum - arr[i - num] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
maxSubarraySum([1, 15, 1, 2, 6, 12, 5, 7], 4); // 30이미지 출처
https://dev.to/mwong068/sliding-window-technique-in-ruby-3og4