[알고리즘&자료구조] 분할정복 알고리즘, Divide and conquer

분할정복이란?

알고리즘 디자인 패러다임 중 하나이다. 

정의 : 문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제(Sub-problem)들로 나누고(Divide) 문제를 해결한 다음(Conquer) 그 결과를 이용해 다시 전체 문제를 해결하며 합치는 방법

---

분할정복 핵심 진행방식

① 분할 : 동일한 타입의 하위 문제로 큰 문제를 분할한다.
② 정복 : 재귀적으로 하위 문제들을 해결한다.
③ 병합 : 적절히 해결된 결과를 사용해 큰 문제를 해결한다.

 

 

---

분할정복 종류

이진탐색, 퀵정렬, 병합(합병)정렬

 

이글에서는 이전 알고리즘&자료구조 글로 썼던 이진탐색의 예시로 진행한다.

---

선형탐색/순차탐색(Linear search, Sequential Search)

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

시간복잡도 O(n)

 

이진탐색(Binary Search)

function search(array, value){
  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;
}