분할과 정복 패턴

JavaScript 알고리즘 & 자료구조 마스터 클래스 강의를 듣고 작성하는 강의노트

분할과 정복 패턴의 개념

한 문제를 둘 이상의 부분으로 분할하여 해결하고 이를 합쳐 원래의 문제를 해결하는 기법으로 주로 배열이나 문자열 같은 큰 규모의 데이터세트를 처리한다.

Example

search 함수는 정렬된 배열과 배열의 인덱스를 가리키는 수를 인자로 받는다. 반드시 '정렬된' 배열이어야 한다.

이러한 구조를 '선형 탐색' 이라고 한다.
시간 복잡도: O(N)

function search(arr, val) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === val) {
      return i;
    }
  }
  return -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], 11); // -1

Refactor

시간 복잡도: Log(N) - 이진 탐색

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

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

    if (array[middle] < val) {
      min = middle + 1;
    } else if (array[middle] > val) {
      max = middle - 1;
    } else {
      return middle;
    }
  }
  return -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], 11); // -1

• 중간 지점(middle)을 찾아 찾고자 하는 수(val)에 대해 크고 작음을 비교한다.

• 찾고자하는 수보다 작다면 중간지점으로부터 이전의 수는 탐색하지 않는다.

• 중간지점으로부터 이후의 배열요소에 대하여 1~2번 절차를 반복한다.

위의 절차와 같이 분할 정복 패턴은 시간을 크게 단축시킬 수 있다.