[Java] 분할 정복 (Divde & Conquer)

참고 블로그
참고 블로그

분할 정복이란?

• 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산
• 각 부분 문제의 답으로부터 전체 문제의 답을 계산함

재귀 호출과 다른 점 -> 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것

---

과정

1) Divde: 문제를 더 작은 문제로 분할
2) Merge: 각 문제에 대한 구한 답을 원래 문제에 대한 답으로 병합
3) Base Case: 더 이상 분할하지 않고 곧장 풀 수 있는 매우 작은 문제

장점

(1) 수열의 빠른 합

• 기존의 재귀호출 시간 복잡도 : sum(n) = 1+2+3+...+n

• 분할 정복 : fastsum(n) = 2*fastsum(n/2) + n2/4(n이 짝수일 때)

• fastsum은 호출될 때마다 최소한 두 번에 한번 꼴로 n이 절반으로 줄어들음

n이 홀수일 경우

• a)의 경우 pow(A,16)과 pow(A,15)를 구하기 위해 pow(A,8)이 두 번 호출됨
  -> 같은 값을 중복으로 계산하는 일이 많기 때문에 m이 증가함에 따라 pow()의 호출 횟수는 m에 대해 선형적으로 증가 -> 분할 정복 의미가 없으며 m-1번 곱셈하는 것과 다른 바 x

• 반면 b에서는 pow()가 O(lgm)개의 거듭제곱에 대해 한번씩 호출됨

-> 이런 중복 문제를 고안하기 위해 만든 것이 동적 계획법

---

병합정렬

• 주어진 수열을 가운데에서 쪼개 비슷한 크기 수열 두 개로 만든 뒤, 재귀 호출을 이용해 정렬한다
• 정렬된 배열을 하나로 합치면서 정렬된 전체 수열을 구함

시간 복잡도

• 수열 크기가 1이 될때까지 절반씩 쪼개 나간 뒤, 정렬된 부분 배열들을 합쳐 나가는 것
• 가은데를 나누기 때문에 O(1)만에 수행할 수 있지만, 배열을 하나로 합치기 위한 merge 과정에서 O(n)의 시간 복잡도 소요

---

퀵 정렬 알고리즘

순서

• 1. 배열에서 피벗 선택 (중간 값, 첫 값, 마지막 값 등 여러 기준으로 선택)
• 2. 피벗을 기준으로 두 개의 서브 배열로 분할 (피벗보다 작으면 왼쪽, 크면 오른쪽)
• 3. 각 서브 배열을 재귀적으로 퀵 정렬
• 4. 정렬된 서브 배열 합침

병합 정렬 알고리즘

• 1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봄
• 2. 그렇지 않으면 리스트를 두 개의 균등한 크기로 분할
• 3. 각 부분 리스트를 재귀적으로 합병 정렬을 통해 정렬
• 4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병

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

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[arr.length];
        int i = left;
        int j = mid + 1;
        int k = left;

        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++];
        }

        for (int index = left; index < k; index++) {
            arr[index] = temp[index];
        }
    }

    public static void main(String[] args) {
        int[] arr = { 5, 2, 4, 7, 1, 3, 2, 6 };
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}