분할 정복 (Divide and Conquer)

분할 정복 (Divide and Conquer) 설명:

분할 정복(Divide and Conquer) 전략은 큰 문제를 더 작은 하위 문제들로 나눈 뒤, 각 하위 문제를 독립적으로 해결하고, 이를 결합하여 원래의 문제를 해결하는 방법입니다. 분할 정복 전략은 주로 재귀적으로 구현됩니다.

분할 정복의 3가지 주요 단계:

1. 분할(Divide): 주어진 문제를 더 작은 하위 문제로 분할합니다.
2. 정복(Conquer): 하위 문제를 재귀적으로 해결합니다.
3. 결합(Combine): 하위 문제의 해답을 합쳐 원래 문제의 해답을 얻습니다.

대표적인 분할 정복 알고리즘:

1. 병합 정렬 (Merge Sort): 주어진 배열을 반으로 나눈 후, 각 부분 배열을 정렬하고, 정렬된 배열들을 합쳐 전체를 정렬합니다.
2. 퀵 정렬 (Quick Sort): 배열에서 피벗(pivot)을 선택하고, 피벗을 기준으로 작은 값들과 큰 값들로 분할한 후, 각 부분 배열을 재귀적으로 정렬합니다.
3. 카라츠바의 곱셈 알고리즘: 큰 수의 곱셈을 효율적으로 계산하기 위해 사용되는 알고리즘입니다.
4. 스트라센의 행렬 곱셈: 행렬의 곱셈을 더 빠르게 수행하기 위한 알고리즘입니다.
5. 가장 가까운 점의 쌍 찾기: 2차원 평면 상의 점들 중에서 가장 가까운 두 점을 찾는 문제입니다.

자바스크립트로의 병합 정렬 구현 예:

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

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

    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let leftIndex = 0, rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));  // 출력: [ 3, 9, 10, 27, 38, 43, 82 ]

분할 정복 전략은 여러 문제에 대한 효율적인 해결 방법을 제공하며, 종종 재귀적 접근 방식과 결합되어 사용됩니다.