[알고리즘] 문제 해결 패턴 (4) 분할 정복 패턴

분할 정복 패턴

주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다.

(연결리스트나 트리가 될 수 있다.)

 

값을 찾기 위해 배열의 왼쪽에서 시작하여 오른쪽 끝까지 이동하는 것보다는 배열을 작은 조각으로 세분화하여 각 조각들을 어디로 이동시킬지 결정하는 작은 조각으로 세분화하여 각 조각들을 어디로 이동시킬지 결정하는 작업을 하겠다.

즉! 큰 데이터 덩어리를 작은 조각으로 나누는것

 

예시

탐색알고리즘의 전형적인 예이다. 이것은 정렬된 숫자를 지닌 배열을 취한다. 배열은 정렬된 상태여야한다. 입력된 search라는 함수는 값을 취하고 해당 값이 있는 위치를 반환시킨다. 

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

 

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

 

o(n)의 시간복잡도이다. 이 구조를 선형 탐색이라고 한다. 

 

리펙토링

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

 

시간 복잡도는 log(n)이다. 이진탐색이다.