[기초]슬라이딩 윈도우 패턴, 분할 정복

Sliding Wind

한 위치에서 다른 위치로 배열 또는 숫자가 될 수 있는 창을 만드는 것을 의미한다.

특정 조건에 따라 창이 증가하거나 닫힌다. (새 창이 생성됨)

 

배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다. 

 

예시를 들어보자.

maxSubarraySum 함수는 정수 배열과 n이라는 숫자를 받아들인다. 

함수는 배열에서 연속되는 n개의 요소의  최대 합계를 계산해야 한다.

 

순수한 해결책

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;
}

배열이 모두 음수로 구성되어 있다면 가장 큰 합이 여전히 음수일 것이기 때문에 max에 -infinity를 선언하였다. 양수로만 작업을 하지 않는 한 0에서 시작하는 것은 여전히 도움이 되지 않는다.

num이 3일 때 동작 방식

[1,2,5,2,3]

[1,2,5,2,3]

[1,2,5,2,3]

maxSubarraySum([1,2,5,2,8,1,5],2) // 10
maxSubarraySum([1,2,5,2,8,1,5],4) // 17
maxSubarraySum([-1,-5,-9,-1,-9,-6], 3) // -15
maxSubarraySum([],4) // null

순수한 해결책은 방대한 배열이 나타나면 모든 항목들을 거치면서 처음부터 합계를 구한다. 매우 비효율적인 코드가 된다.

 

그래서 슬라이딩 윈도우 패턴을 이용해 리펙토링 해보자.

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];
  }
  tempSum = maxSum;
  for(let i = num; i < arr.length; i++) {
    // arr[i - num] 합산의 맨 앞 숫자 + arr[i] 합산의 다음 첫 숫자  
    tempSum = tempSum - arr[i - num] + arr[i];
    // tempSum이 maxSum보다 크면 maxSum을 갱신
    maxSum = Math.max(maxSum, tempSum);
  }
return maxSum;
}

시간 복잡도 - O(N)

위 코드는 루프가 한 번만 적용되기에 O(N)의 선형 복잡도를 가진다. 

num이 3일 때 동작 방식      빼는 부분,      더하는 부분

[1,2,5,2,3]

[1,2,5,2,3]

[1,2,5,2,3]

다음 합계를 구하기 위해 맨 앞의 숫자를 빼고 다음 숫자를 더한다.

이것이 슬라이딩 윈도우이다. 새로운 합을 계속해서 진행하는 것이 아니라 앞의 숫자를 뺀 다음 창문을 다음으로 이동시키고 새롭게 포함된 맨 뒤 숫자를 더하는 것이다.

중첩 루프로 연속적으로 루프를 진행할 필요 없이 매 루프를 통해 한번씩 덧셈과 뺄셈을 수행하면 된다. 이것이 슬라이딩 윈도우 기능이며 매우 효율적이다. 

 

분할 정복(Divide and Conquer)

큰 문제를 작은 문제로 쪼개어서 푼 후 합쳐서 전체 문제의 답을 찾는 방법이다. 

시간 복잡성을 크게 줄일 수 있다. 

 

예시를 들어 알아보자.

정렬된 정수 배열이 주어지면 값을 받아들이고 함수에 전달된 값이 있는 인덱스를 반환하는 search함수. 값을 찾을 수 없으면 -1 반환.

search([1,2,3,4,5,6], 4) // 3
search([1,2,3,4,5,6], 6) // 5
search([1,2,3,4,5,6], 9) // -1

순진하고 쉬운 접근법은 왼쪽에서 시작하여 살펴보는 것이다. 11을 찾는 경우, 왼쪽부터 시작하여 숫자가 11인지 살펴본다. 전체 배열에 루프하여 O(N)이 된다. 

function search(arr, num) {
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] === num) {
      return i
    }
  }
  return -1;
}

위와 같은 구조를 선형 탐색(Linear Search)이라고 하는데 O(N)의 복잡도를 가진다. 

 

function search(arr, val) {
  let min = 0;
  let max = arr.length - 1;

  while (min <= max) {
    let middle = Math.floor((min + max) / 2);
    let currentElement = arr[middle];

    if(arr[middle] < val) {
      min = middle + 1;
    } else if (arr[middle] > val) {
      max = middle -1;
    } else {
      return middle;
    }
  }
return -1;
}

위 코드는 Log(N)의 시간 복잡도를 가지는 이진 탐색(Binary Search) 알고리즘이다. 

분할과 정복이 보편적으로 쓰이는 패턴이며 간단하게 알아보았다.