서론
오늘 공부한 것은 슬라이딩 윈도우 알고리즘이다. 슬라이딩 윈도우라는 단어는 익숙하다. 정처기 공부할 때 네트워크 호스트간의 패킷의 흐름을 조절해주는 것으로 달달 외웠었는데 여기서 같은 이름의 알고리즘 이름으로 만나니 반가울 따름이다. 본론에서 이어서 슬라이딩 윈도우 알고리즘에 대해 알아보도록 하겠다.
본론
슬라이딩 윈도우란?
고정사이즈의 창문, 윈도우를 만들고 조건에 따라 이동하면서 윈도우 내의 데이터로 문제를 풀이하는 것을 말한다. 슬라이딩 윈도우 알고리즘은 배열이나 스트링 같은 연속적인 데이터를 세팅할때 또 규모가 큰 연속적인 데이터셋 에서 데이터 하위값을 추적하는 문제에서 유용하다.
예시1
주어진 배열에서 연속된 합의 가장 큰 숫자를 구하시오.
[1,5,8,5,3,2,9,1,5,6,4] 4
다음과 같은 배열과 몇개의 연속된 숫자를 더해야하는지를 지시하는 숫자 이렇게 두개의 데이터가 매개변수로 들어왔을때, 합이 제일 큰 것을 반환하면 되는 문제이다. 우리는 이 문제를 두가지 방식으로 접근해서 풀어보려고 한다. 먼저 Navie한 간단하게 떠올릴 수 있는 for문을 이용한 해답이다.
Naive한 해결책
for문을 이용한 해결책
function getMaxSum(arr, num){
//num보다 arr이가 짧고, null인 경우를 대비.
if(num > arr.length) return null;
//arr에 음수의 값만이 넘어왔을때를 대비하여 -infinity를 설정
//범위 내 모든 값이 양수라면 0으로 설정해도 되나, 최댓값이 음수일 경우에는 기본값인 0을 넘지 못한게 된다.
//그러니 가장 작은 값을 초기값으로 설정한다. (=Integer.MIN_VALUE)
var maxSum = -Infinity;
//num 숫자만큼의 배열요소가 남지 않았을때 for문을 빠져나올 수 있도록
for(let i=0; i<arr.length - num + 1; i++){
var tempSum = 0;
for(let j=0; j < num; j++){
tempSum += arr[i + j];
}
//최댓값 비교 및 세팅
if(tempSum > maxSum){
maxSum = tempSum;
}
}
return maxSum;
}다음과 같은 풀이로 진행하면 시간 복잡도 O(n^2)의 코드가 만들어진다. 예시로 주어진 것과 같이 작은 데이터라면 괜찮지만, 데이터의 크기가 커지면 커질수록 느려지고 성능이 나빠진다. 때문에 좋은 방법이라고는 할 수 없다. 다음은 슬라이딩 윈도우 알고리즘으로 접근하며 리팩토링 해보도록 하겠다.
Refactoring
슬라이딩 윈도우 알고리즘으로 접근한 해결책
function getMaxSum(arr, num){
var maxSum = -infinity;
var tempSum = 0;
//num보다 arr이가 짧고, null인 경우를 대비.
if(num > arr.length) return null;
//먼저 num만큼 연속된 숫자를 더하고 maxSum에 초기값을 저장한다.
for(let i=0; i<num; i++){
maxSum += arr[i];
}
tempSum = maxSum;
for(let i = num; i<arr.length; i++){
//맨 처음의 요소를 빼고 맨 뒤의 요소를 더한다.
tempSum = tempSum - arr[i-num] + arr[i];
//최댓값 비교 (Max를 이용해서 비교하는 것도 가능하다!)
if(tempSum > maxSum) maxSum = tempSum;
}
return maxSum;
}이렇게 O(n)의 시간복잡도의 코드가 만들어졌다. 슬라이딩 윈도우 알고리즘은 다음과 같이 문제를 수학적으로 접근하여 맨 앞과 맨 뒤에 있는 데이터를 빼고 더하는 것으로 매번 num만큼의 숫자를 더하는 수고를 덜게 해준다. 단지 for문을 이용한 나이브한 문제가 중첩된 for루프로 num만큼의 숫자를 더하는 것을 반복하는데 지금은 데이터의 크기가 작아서 문제가 없지만, 데이터의 크기가 커지고 num이 커지면 연산에 시간이 많이 걸리게 된다.
참고
