분할 정복 알고리즘 (Divide and Conquer)

분할 정복(Divide and Conquer)은 문제를 작은 부분으로 나누고, 각 부분을 개별적으로 해결한 후, 그 결과를 합쳐 최종 문제를 해결하는 알고리즘 설계 기법입니다. 주로 재귀적으로 문제를 해결하며, 복잡한 문제를 간단한 작은 문제로 분리하여 효율적으로 처리할 수 있습니다.

분할 정복의 3단계

분할 (Divide): 문제를 더 작은 하위 문제로 나눕니다.
정복 (Conquer): 각 하위 문제를 재귀적으로 해결합니다. 하위 문제가 충분히 작으면 직접 해결합니다.
결합 (Combine): 하위 문제의 결과를 결합하여 원래 문제를 해결합니다.

이제 대표적인 분할 정복 알고리즘인 퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)을 살펴보겠습니다.

1. 퀵 정렬 (Quick Sort)

퀵 정렬은 피벗(pivot)을 기준으로 리스트를 두 부분으로 나눈 다음, 재귀적으로 각 부분을 정렬하는 알고리즘입니다. 퀵 정렬은 평균적으로 매우 빠르며, 대부분의 경우 효율적으로 작동합니다. 시간 복잡도는 평균적으로 O(n log n)입니다.

퀵 정렬의 과정

리스트에서 피벗 값을 선택합니다. 피벗은 리스트의 아무 값이나 될 수 있지만, 주로 첫 번째나 마지막 값을 선택합니다.
피벗보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치하여 리스트를 두 개로 분할합니다.
각각의 하위 리스트에 대해 다시 퀵 정렬을 재귀적으로 수행합니다.
모든 하위 리스트가 정렬되면, 이를 합쳐 최종적으로 정렬된 리스트를 얻습니다.

퀵 정렬 예제 코드


// 퀵 정렬 예제 코드 (JavaScript)
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;  // 배열의 길이가 1 이하일 때는 이미 정렬됨
    }
    let pivot = arr[Math.floor(arr.length / 2)];  // 피벗 설정 (중간 값)
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if (i === Math.floor(arr.length / 2)) continue;  // 피벗 제외
        if (arr[i] < pivot) left.push(arr[i]);  // 피벗보다 작은 값은 왼쪽
        else right.push(arr[i]);  // 피벗보다 큰 값은 오른쪽
    }
    return quickSort(left).concat([pivot], quickSort(right));
}

let array = [34, 7, 23, 32, 5, 62];
console.log(quickSort(array));  // [5, 7, 23, 32, 34, 62]

퀵 정렬은 리스트를 재귀적으로 분할하여 정렬하므로, 평균적으로 O(n log n)의 성능을 보입니다. 그러나 최악의 경우(이미 정렬된 리스트에서 매번 가장 작은 값을 피벗으로 선택하는 경우) 시간 복잡도가 O(n²)가 될 수 있습니다.

2. 병합 정렬 (Merge Sort)

병합 정렬은 리스트를 절반씩 나누어 각각을 재귀적으로 정렬한 후, 두 리스트를 병합하여 하나의 정렬된 리스트로 만드는 알고리즘입니다. 병합 정렬은 항상 안정적인 성능을 보장하며, 시간 복잡도는 항상 O(n log n)입니다.

병합 정렬의 과정

리스트를 절반으로 나눕니다. 리스트의 길이가 1이 될 때까지 반복합니다.
각각의 하위 리스트를 재귀적으로 병합 정렬합니다.
정렬된 두 하위 리스트를 병합하여 하나의 정렬된 리스트로 만듭니다.

병합 정렬 예제 코드


// 병합 정렬 예제 코드 (JavaScript)
function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;  // 배열의 길이가 1 이하일 때는 이미 정렬됨
    }
    let mid = Math.floor(arr.length / 2);
    let left = mergeSort(arr.slice(0, mid));  // 왼쪽 절반 재귀적 정렬
    let right = mergeSort(arr.slice(mid));  // 오른쪽 절반 재귀적 정렬
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) {
            result.push(left.shift());  // 왼쪽 리스트에서 작은 값 추가
        } else {
            result.push(right.shift());  // 오른쪽 리스트에서 작은 값 추가
        }
    }
    return result.concat(left, right);  // 남은 값들을 결과에 병합
}

let array = [34, 7, 23, 32, 5, 62];
console.log(mergeSort(array));  // [5, 7, 23, 32, 34, 62]

병합 정렬은 리스트를 계속해서 분할하고, 분할된 리스트들을 병합하는 방식으로 동작합니다. 이 과정에서 추가적인 메모리 공간이 필요합니다.

퀵 정렬과 병합 정렬의 비교

퀵 정렬과 병합 정렬은 모두 분할 정복 알고리즘에 속하며, 다음과 같은 특징을 가집니다.

특징	퀵 정렬 (Quick Sort)	병합 정렬 (Merge Sort)
시간 복잡도 (평균)	O(n log n)	O(n log n)
시간 복잡도 (최악)	O(n²)	O(n log n)
추가 메모리	거의 필요 없음 (제자리 정렬)	추가적인 메모리 필요 (병합 과정에서)
안정성	비안정 정렬	안정 정렬

퀵 정렬은 평균적으로 매우 빠르지만, 최악의 경우 시간 복잡도가 O(n²)까지 나빠질 수 있습니다. 반면, 병합 정렬은 항상 O(n log n)의 성능을 보장하지만 추가 메모리가 필요합니다. 두 알고리즘 모두 데이터의 특성과 상황에 따라 적절하게 선택해야 합니다.

결론

분할 정복 알고리즘은 문제를 작은 부분으로 나누어 처리하는 방식으로, 복잡한 문제를 효율적으로 해결할 수 있습니다. 퀵 정렬과 병합 정렬은 대표적인 분할 정복 알고리즘으로, 각각의 장단점이 있으므로 문제의 특성에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.

DAILY IS COMING

분할 정복 알고리즘 (Divide and Conquer) 요약