2.4Divide and Conquer

Divide and Conquer

Divide and Conquer(분할 정복) 패턴은 문제를 더 작고 동일한 구조의 문제로 분할(divide)하고, 그 각각을 재귀적 또는 반복적으로 해결(conquer)하여 전체 문제를 푸는 전략이다.

이 패턴은 정렬이나 탐색처럼 대규모 데이터를 효율적으로 처리할 때 매우 유용하며, 대표적인 예로 Binary Search, Merge Sort, Quick Sort 등이 있다.

예시 1:

정렬된 정수 배열이 주어졌을 때, 특정 값이 존재하는 인덱스를 반환하는 함수를 작성하라.

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

비효율적인 풀이는 아래와 같다. Linear Search라고 하는 방식으로, 단순히 for 루프로 처음부터 끝까지 찾는 방식이다. O(n)의 시간 복잡도를 가진다.

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

다음은 효율적인 방식으로, Binary Search라고도 한다. 배열이 정렬된 것을 이용하는 방법으로, 중앙 값을 기준으로 좌우를 나눠가며 탐색을 반복한다. 시간 복잡도가 O(log n)으로 줄어든다.

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

Divide and Conquer는 특히 탐색, 정렬에 많이 쓰이는 패턴으로 앞으로도 많이 볼 수 있을 것이다.