슬라이딩 윈도우 패턴
August 10, 2022
JavaScript 알고리즘 & 자료구조 마스터 클래스 강의를 듣고 작성하는 강의노트
* '슬라이딩 윈도우(Sliding Window)'이라는 명칭은 공식 명칭이 아니다. 본 글에서는 이를 '슬라이딩 윈도우'라고 명명한다.
슬라이딩 윈도우 패턴의 개념
배열이나 리스트 요소의 일정 범위의 값을 비교할 때 사용하면 유용한 알고리즘이다.
예를 들어 한 단어의 문자들 중 연속된 고유 문자의 길이가 가장 긴 부분을 출력할 때
슬라이딩 윈도우와 같은 패턴을 사용할 수 있다.
ex. 'hellothere' 에서는 'lother' 가 가장 길다.)
대표적인 예제를 통해 살펴보자.
Example
maxSubarraySum
함수가 있다.- 첫번째 인자로 하나의 배열을 전달 받는다.
- 두번째 인자로 한 숫자로 전달 받는다.
- 인자로 받은 배열 내, 두번째 인자만큼 연속된 숫자들의 합이 가장 큰 숫자들의 합을 반환하는 함수다.
- 배열의 수가 두번째 인자보다 작을 때 null을 반환한다.
function maxSubarraySum(arr, num) {
if (num > arr.length) {
return null;
}
let max = -Infinity;
for (let i = 0; i < arr.length - num + 1; i++) {
temp = 0;
for (let j = 0; j < num; j++) {
temp += arr[i + j];
}
if (temp > max) {
max = temp;
}
}
return max;
}
maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 2); // 10
maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4); // 17
maxSubarraySum([4, 2, 1, 6], 1); // 6
maxSubarraySum([4, 2, 1, 6, 2], 4); // 13
maxSubarraySum([], 4); // null
*
max
를-Infinity
로 표현한 것은 배열이 음수로 구성되어 있을 경우 가장 큰 합 또한 음수일 것이기 때문이다.
Nested loop(중첩 루프)로 인해 시간 복잡도는 O(N2)
위와 같이 간단한 예제에서는 문제가 되지 않지만 방대한 길이의 배열, 방대한 양의 수만큼의 합을 구하게 된다면 굉장히 비효율적인 방식이 될 것이다. 이를 슬라이딩 윈도우 패턴을 통해 리팩토링 해보자.
Refactor
function maxSubarraySum(arr, num) {
let maxSum = 0;
let tempSum = 0;
if (arr.length < num) return null;
for (let i = 0; i < num; i++) {
maxSum += arr[i];
}
temSum = maxSum;
for (let i = num; i < arr.length; i++) {
tempSum = tempSum - arr[i - num] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
위의 함수를 아래와 같이 호출한다고 할 때,
maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3, 4, 1, 3, 6, 5, 6], 5);
먼저
2, 6, 9, 2, 1
부분을 검사하고
다음6, 9, 2, 1, 8
부분을 검사하고
그 다음9, 2, 1, 8, 5
부분을 검사하고 ...
위 과정을 반복하는데 처음 더한 합에서 첫번재 수를 빼고 다음 루프의 첫번째 수를 더하기만 하면 된다.
tempSum = tempSum - arr[i - num] + arr[i];
시간 복잡도: O(N)