알고리즘, 문제해결패턴, Divide and Conquer

Divide and Conquer

Divide and Conquer의 기본 개념은 다음과 같습니다:

1. 분할(Divide): 해결해야 할 문제를 동일한 유형의 더 작은 부분 문제로 나눕니다.
2. 정복(Conquer): 각 부분 문제를 재귀적으로 해결합니다. 부분 문제가 충분히 작으면 직접 해결합니다.
3. 결합(Combine): 부분 문제의 해를 합쳐서 원래 문제의 해를 얻습니다.

예제

예제 1: 병합 정렬 (Merge Sort)

병합 정렬은 Divide and Conquer를 사용하는 대표적인 정렬 알고리즘입니다. 배열을 반으로 나눈 후 각각을 정렬하고, 정렬된 부분 배열을 합칩니다.

function merge(arr1, arr2) {
  let idx1 = 0;
  let idx2 = 0;
  let result = [];

  while (idx1 < arr1.length && idx2 < arr2.length) {
    if (arr1[idx1] < arr2[idx2]) {
      result.push(arr1[idx1]);
      idx1++;
    } else {
      result.push(arr2[idx2]);
      idx2++;
    }
  }

  // Remaining elements from arr1
  while (idx1 < arr1.length) {
    result.push(arr1[idx1]);
    idx1++;
  }

  // Remaining elements from arr2
  while (idx2 < arr2.length) {
    result.push(arr2[idx2]);
    idx2++;
  }

  return result;
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

console.log(mergeSort([8, 3, 5, 4, 7, 6, 1, 2]));

예제 2: 이진 탐색 (Binary Search)

이진 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘입니다. 배열을 반으로 나누어 찾고자 하는 값이 어느 쪽에 있는지 확인한 후, 해당 절반에서 다시 탐색을 반복합니다.

function binarySearch(arr, target) {
  var start = 0;
  var end = arr.length - 1;
  var middle = Math.floor((start + end) / 2);
  
  while (arr[middle] !== target && start <= end) {
    if (target < arr[middle]) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
    middle = Math.floor((start + end) / 2);
  }
  if (arr[middle] === target) {
    return middle;
  }
  return -1;
}

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(binarySearch(arr, 7)); // 6
console.log(binarySearch(arr, 11)); // -1

시간 복잡도

Divide and Conquer를 사용하는 알고리즘의 시간 복잡도는 문제의 종류에 따라 다릅니다. 예를 들어:

• 병합 정렬: O(n log n)
• 이진 탐색: O(log n)

활용 예시

Divide and Conquer 기법은 다음과 같은 다양한 문제에서 유용하게 사용됩니다:

• 정렬 알고리즘 (예: 병합 정렬, 퀵 정렬)
• 검색 알고리즘 (예: 이진 탐색)
• 행렬 곱셈 (Strassen 알고리즘)
• 큰 수의 곱셈 (Karatsuba 알고리즘)
• 최근접 점 문제

이 기법은 복잡한 문제를 더 작은 문제로 분할하여 해결하기 때문에 매우 효율적이며, 많은 알고리즘에서 핵심적인 역할을 합니다.