분할과 정복 패턴

📌 분할과 정복 패턴

큰 문제를 작은 문제로 쪼개어서 푼 후 합쳐서 전체 문제의 답을 찾는 기법으로 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다.

 

👀 Example 1

• search 함수는 정렬된 배열을 첫 번째 인자로 받는다.
• 두 번째 인자로 전달된 숫자의 위치(인덱스)를 반환한다.

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],11) // -1

Solution

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

일반적인 방식으로 반복문을 이용해 배열의 각 요소에 하나하나씩 접근(선형 탐색)하여 값을 도출할 수 있다. 이 방식의 시간 복잡도는 O(N)이다.

Refactored

function search(array, val) {
    let min = 0;
    let max = array.length - 1;
 
    while (min <= max) {
        let middle = Math.floor((min + max) / 2);
        let currentElement = array[middle];
 
        if (array[middle] < val) {
            min = middle + 1;
        }
        else if (array[middle] > val) {
            max = middle - 1;
        }
        else {
            return middle;
        }
    }
 
    return -1;
}

위의 방식이 분할과 정복 패턴을 사용한 이진 탐색이다.

• 중간 지점을 찾아 val에 대한 범위를 찾는다.
• 범위가 val보다 작으면 해당 범위에서는 탐색하지 않는다.
• 중간 지점으로부터 이후의 배열 요소에 대해 위의 사항을 반복한다.

분할과 정복 패턴을 사용하면 시간을 크게 단축시킬 수 있다. 이 패턴의 시간복잡도는 O(log N)이다.