분할정복(Divide and Conquer)

1. 분할정복(Divide and Conquer)이란?

- 분할정복은 문제를 작은 하위 문제로 분할(Divide)하고 각각을 재귀적으로 해결(Conquer)한 뒤 다시 합쳐(Merge) 전체 문제의 해답을 얻는 알고리즘 기법이다.

- 대표적으로 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 큰 수 거듭제곱 문제 등이 있다.

 

1-1. 핵심 아이디어

- 분할(Divide): 해결하고자 하는 문제를 더 이상 분할할 수 없거나 충분히 작아질 때까지 여러 하위 문제로 나눈다.

- 정복(Conquer): 분할된 하위 문제를 재귀적으로 해결한다.

- 병합(Merge): 각각의 하위 문제에서 구한 해답을 병합하여 원래 문제의 답을 도출한다.

 

1-2. 장점 및 단점

- 장점: 큰 문제를 여러개의 작은 문제로 나누어 논리적 단순화가 가능, 병렬처리나 캐싱에 유리하다

- 단점: 잘못된 분할 기준 설정 시 재귀 호출이 많아져 효율이 떨어질 수 있다

 

2. 분할정복 활용 문제

2-1. 병합 정렬(Merge Sort)

- 병합 정렬은 배열을 절반으로 계속 나눈 뒤, 각 하위 배열을 정렬하고 이를 정렬된 상태로 합치는 과정으로 동작한다.

- O(NlogN)의 시간복잡도를 가진다.

public class MergeSort {
    public static void merge(int[] arr, int left, int mid, int right) {
        // 임시 배열에 병합 결과를 저장
        int[] temp = new int[right-left-1];
        int i = left;
        int j = mid+1;
        int k = 0;

        // 양쪽 부분 배열을 비교하며 작은 값부터 삽입
        while(i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 왼쪽 부분에 남은 데이터 삽입
        while(i <= mid) {
            temp[k++] = arr[i++];
        }

        // 오른쪽 부분에 남은 데이터 삽입
        while(j <= right) {
            temp[k++] = arr[j++];
        }

        // temp 배열의 원소를 다시 arr에 복사
        for(int t = 0; t < temp.length; t++) {
            arr[left+t] = temp[t];
        }
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if(left < right) {
            int mid = (left+right)/2;

            // Divide: 왼쪽 절반, 오른쪽 절반으로 나눠서 재귀 호출
            mergeSort(arr, left, mid);
            mergeSort(arr, mid+1, right);

            // Combine: 정렬된 두 부분을 병합
            merge(arr, left, mid, right);
        }
    }

    public static void main(String[] args) {
        // 예제 데이터
        int[] arr = {5, 2, 9, 1, 7, 3};

        // 병합 정렬 수행
        mergeSort(arr, 0, arr.length-1);

        // 출력: 1 2 3 5 7 9
        for(int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

2-2. 퀵 정렬(Quick Sort)

- 퀵 정렬은 배열에서 하나의 기준 원소(pivot)을 정하고 피벗보다 작거나 같은 요소들은 왼쪽, 피벗보다 큰 요소들은 오른쪽으로 배치하여 재귀적으로 정렬한다.

- 평균의 시간복잡도는 O(NlogN), 최악의 시간복잡도는 O(N^2)이다.

public class QuickSort {

    // 배열을 분할하여 피벗의 최종 위치를 반환
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right]; // 맨 오른쪽 요소를 피벗으로 선택
        int i = left-1; // i: 피벗보다 작거나 같은 요소들의 끝지점

        for(int j = left; j < right; j++) {
            // 피벗보다 작거나 같은 경우 왼쪽 파티션으로 교환
            if(arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i+1];
        arr[i+1] = arr[right];
        arr[right] = temp;

        return i+1;
    }

    public static void quickSort(int[] arr, int left, int right) {
        if(left <= right) {
            // Conquer: 파티션 함수로 피벗의 위치를 얻고 왼쪽/오른쪽 각각 정렬
            int pivotIndex = partition(arr, left, right);

            quickSort(arr, left, pivotIndex-1);
            quickSort(arr, pivotIndex+1, right);
        }
    }

    public static void main(String[] args) {
        // 예제 데이터
        int[] arr = {10, 7, 8, 9, 1, 5};

        // 퀵 정렬 수행
        quickSort(arr, 0, arr.length-1);

        // 출력: 1 5 7 8 9 10
        for(int num : arr) {
            System.out.print(num + " ");
        }
    }
}