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


## 분할 정복이란?

- 하나의 문제를 작은 부분 문제로 나누어 해결하는 알고리즘
- 문제를 분할하고, 각 부분 문제를 해결하여 전체 문제의 해결책을 찾는다
- 분할 정복 알고리즘은 다음과 같은 세 단계로 이루어진다
- 분할(Divide) 단계: 문제를 작은 부분 문제로 분할한다
- 정복(Conquer) 단계: 부분 문제를 해결한다
- 결합(Combine) 단계: 부분 문제의 해결책을 결합하여 전체 문제의 해결책을 구한다
- 장점
- 문제를 나누어서 해결하므로, 병렬 처리에 적합하다
- 문제를 나누어서 해결하기 때문에, 코드가 간결하고 이해하기 쉽다
- 분할된 문제가 서로 독립적이기 때문에, 처리 속도가 빠르다
- 단점
- 분할 단계에서 부분 문제를 작게 나누면 오버헤드가 발생하여 실행 시간이 증가할 수 있다
- 일반적으로 재귀 함수를 사용하므로, 함수 호출에 따른 오버헤드가 발생할 수 있다
- 반드시 재귀를 사용해야 하는 것은 아니며, 반복문을 사용하여 구현할 수도 있다

> 분할정복과 재귀함수
>
> - 분할정복과 재귀함수는 유사하지만 기본 원리와 적용 방식에 차이가 있다
> - 재귀 알고리즘은 문제를 해결하기 위해 자기 자신을 호출하는 방식으로 동작하며, 이는 분할 정복 알고리즘의 한 가지 구현 방식일 뿐이며, 두 알고리즘은 독립적인 개념으로 이해해야 한다.
> - 분할 정복은 문제를 부분 문제로 나누고, 각 부분 문제를 정복하여 원래 문제의 해결책을 찾는 전략이며, 재귀 알고리즘은 함수가 자기 자신을 다시 호출하는 방식으로 문제를 해결하는 전략
> - 분할 정복 알고리즘은 문제를 작은 부분으로 나누어 해결하는 접근 방식이기 때문에, 재귀 함수가 아닌 반복문을 사용하여 구현할 수도 있다. 예를 들어 이진 검색 알고리즘은 반복문을 사용하여 구현할 수도 있으며, 이 경우에도 작은 부분 문제로 나누어 해결하는 분할 정복 알고리즘의 전략을 따른다

## 분할 정복 알고리즘 예시

1. 병합 정렬(Merge Sort)
- 정렬되지 않은 배열이 주어졌을 때, 분할 정복 알고리즘을 이용하여 배열을 정렬하는 문제
2. 퀵 정렬(Quick Sort)
- 정렬되지 않은 배열이 주어졌을 때, 분할 정복 알고리즘을 이용하여 배열을 정렬하는 문제
3. 색종이 만들기 문제
- N * N 크기의 2차원 배열이 주어졌을 때, 배열을 4개의 분할 영역으로 나누어 색종이의 개수를 구하는 문제
- 백준 알고리즘 2630번 ==[링크](https://www.acmicpc.net/problem/2630)==
4. 쿼드 트리 문제
- N * N 크기의 2차원 배열이 주어졌을 때, 배열을 압축하는 문제
- 백준 알고리즘 1992번 ==[링크](https://www.acmicpc.net/problem/1992)==

> 일반적으로 다음과 같은 특징이 보이면 분할 정복 알고리즘을 고려해본다
>
> - 문제를 독립적인 부분 문제로 나눌 수 있는 경우
> - 부분 문제의 해답을 병합하는 과정이 존재하는 경우
> - 중복되는 부분 문제가 없는 경우
> - 재귀적 구조를 가지고 있는 경우

### 병합 정렬 (Merge sort)


- 배열을 반으로 나누어 각각을 정렬한 후, 정렬된 두 배열을 병합하여 전체를 정렬하는 알고리즘
- 원리
1. 분할(Divide): 주어진 배열이나 리스트를 반으로 나눈다. 이 과정을 더 이상 나눌 수 없을 때까지 반복한다. 이렇게 되면 모든 부분 배열은 하나의 원소를 가지게 된다.
2. 정복(Conquer): 가장 작은 부분 배열(하나의 원소를 가진 배열)부터 시작하여, 인접한 두 부분 배열을 정렬하면서 병합한다. 이렇게 정렬된 배열은 다시 인접한 정렬된 배열과 병합되어 최종 정렬된 배열을 얻을 때까지 반복한다.
3. 병합(Merge): 인접한 두 부분 배열을 정렬하면서 병합하는 과정. 각 부분 배열의 첫 번째 원소를 비교하여 더 작은 값을 결과 배열에 넣고, 해당 원소를 부분 배열에서 제거한다. 이 과정을 두 부분 배열의 원소가 모두 소진될 때까지 반복한 후, 남은 원소가 있는 배열의 나머지 원소를 결과 배열에 추가한다.
- 
- 장점
- 안정적인 정렬 알고리즘으로, 입력 데이터의 분포와 순서에 영향을 받지 않는다.
- 최악의 경우에도 시간 복잡도가 `O(nlogn)`으로 빠르며, 대부분의 경우에 빠른 실행 속도를 보인다.
- 분할 정복 알고리즘을 사용하므로, 병렬 처리가 가능하다.
- 추가적인 메모리가 필요하지만, 입력 데이터의 크기가 크더라도 메모리 사용량이 고정적이며, 크기가 큰 데이터에 대해서도 처리가 가능하다.
- 단점
- 입력 데이터의 크기가 작은 경우에는 다른 정렬 알고리즘들보다 느린 실행 속도를 보일 수 있다.
- 추가적인 메모리 공간이 필요하므로, 메모리 사용량이 더 많아질 수 있다.
- 합병 과정에서 인덱스를 이동하는 등의 연산이 필요하므로, 다른 알고리즘들보다 연산 속도가 느릴 수 있다.
- 시간 복잡도 : `O(nlogn)`
- 분할 단계에서 배열을 반으로 나누는 과정은 `O(logn)`의 시간 복잡도를 가진다.
- 병합 단계에서 두 부분 배열을 병합하는 과정은 `O(n)`의 시간 복잡도를 가진다.
- 따라서, 전체 병합 정렬의 시간 복잡도는 `O(nlogn)`이 된다.

#### 병합 정렬 코드 예

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 = {21, 10, 12, 20, 25, 13, 15, 22};
        int left = 0;
        int right = arr.length - 1;

        mergeSort(arr, left, right);

        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

### 퀵 정렬 (Quick sort)


- pivot 값을 기준으로 배열을 두 부분으로 분할하고, 각 부분을 재귀적으로 정렬하는 알고리즘
- 추가 메모리를 거의 사용하지 않는 인플레이스(in-place) 정렬 알고리즘이기 때문에, 메모리 사용량 측면에서 장점이 있다
- 원리
1. 피벗 선택(Select Pivot): 배열에서 피벗 엘리먼트를 선택한다. 피벗을 선택하는 방법에는 여러 가지가 있으며, 일반적으로는 배열의 첫 번째 원소, 마지막 원소 또는 무작위로 선택한 원소를 사용한다.
2. 분할(Partition): 피벗을 기준으로 배열을 두 부분으로 분할한다. 피벗보다 작은 값은 피벗 왼쪽에 위치하고, 피벗보다 큰 값은 피벗 오른쪽에 위치하게 된다. 분할 작업이 완료되면, 피벗은 최종 정렬 위치에 있게 된다.
3. 재귀 정렬(Recursive Sort): 피벗을 제외한 왼쪽 부분 배열과 오른쪽 부분 배열을 다시 퀵 정렬로 정렬한다. 이 과정은 부분 배열의 크기가 1 또는 0이 될 때까지 재귀적으로 반복된다.
- 
- 장점
- 평균적으로 가장 빠른 실행 속도를 보이는 정렬 알고리즘 중 하나
- 입력 데이터의 크기가 큰 경우에도 빠른 실행 속도를 보인다
- 추가적인 메모리 공간이 필요하지 않으므로, 메모리 사용량이 적다
- 분할 정복 알고리즘을 사용하므로, 병렬 처리가 가능하다
- 단점
- pivot 값을 잘못 선택하면, 최악의 경우에는 시간 복잡도가 `O(n^2)`까지 증가할 수 있다. 이를 방지하기 위해, pivot 값을 잘 선택하는 것이 중요하다
- 입력 데이터가 무작위로 주어지는 경우에는 평균적으로 빠른 실행 속도를 보이지만, 이미 정렬되어 있는 경우나 입력 데이터의 분포가 균일하지 않은 경우에는 실행 속도가 저하될 수 있다
- 항상 안정적인 정렬을 보장하지 않는다
- 시간복잡도
- 평균 : `O(nlogn)`
- 최악 : `O(n^2)`

#### 퀵 정렬 코드 예

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);  // 피벗을 선택하고, 분할 작업을 수행한다
            quickSort(arr, left, pivot - 1);  // 피벗을 기준으로 왼쪽 부분 배열을 정렬한다
            quickSort(arr, pivot + 1, right);  // 피벗을 기준으로 오른쪽 부분 배열을 정렬한다
        }
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];  // 피벗을 오른쪽 끝 요소로 선택한다
        int i = left - 1;  // 피벗보다 작은 요소들을 저장할 인덱스

        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);  // 피벗보다 작은 요소를 왼쪽으로 이동시킨다
            }
        }
        swap(arr, i + 1, right);  // 피벗을 정렬된 위치로 이동시킨다
        return i + 1;  // 피벗의 인덱스를 반환한다
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {21, 10, 12, 20, 25, 13, 15, 22};
        int left = 0;
        int right = arr.length - 1;

        quickSort(arr, left, right);  // 퀵 정렬을 수행한다

        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

> 안정 정렬 (Stable Sort)이란 중복된 값을 입력 순서와 동일하게 정렬하는 알고리즘의 특성을 의미한다.
>
> - 안정 정렬 : 삽입정렬, 병합정렬, 버블정렬
> - 불안정 정렬 : 선택정렬, 퀵정렬

### 색종이 만들기 문제

- 백준 알고리즘 2630번 ==[링크](https://www.acmicpc.net/problem/2630)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 색종이 만들기 문제 수도코드 예

1. N * N 크기의 2차원 배열을 입력받는다.
2. 전체 배열에 대해 모든 원소가 같은 색인지 검사한다.
    a. 모든 원소가 같다면 해당 색의 색종이 개수를 1 증가시킨다.
    b. 하나라도 다른 색이 있다면, 4개의 분할 영역으로 나눈다.
3. 각 분할된 영역에 대해 재귀적으로 2번 과정을 반복한다.
4. 최종적으로 흰색과 파란색 색종이의 개수를 출력한다.

#### 색종이 만들기 문제 소스코드 예

import java.io.*;
import java.util.Scanner;

public class Main {
    static int[][] map;
    static int white = 0, blue = 0;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            String[] row = sc.nextLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(row[j]);
            }
        }

        divide(0, 0, N);
        System.out.println(white);
        System.out.println(blue);
    }

    static void divide(int x, int y, int size) {
        if (checkColor(x, y, size)) {
            if (map[x][y] == 0) white++;
            else blue++;
            return;
        }

        int newSize = size / 2;

        divide(x, y, newSize);
        divide(x, y + newSize, newSize);
        divide(x + newSize, y, newSize);
        divide(x + newSize, y + newSize, newSize);
    }

    static boolean checkColor(int x, int y, int size) {
        int color = map[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (map[i][j] != color) {
                    return false;
                }
            }
        }
        return true;
    }
}

### 쿼드 트리 문제

- 백준 알고리즘 1992번 ==[링크](https://www.acmicpc.net/problem/1992)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 쿼드 트리 문제 수도코드 예

1. N * N 크기의 2차원 배열을 입력받는다.
2. 전체 배열에 대해 모든 원소가 같은 값인지 검사한다.
    a. 모든 원소가 같다면 해당 원소(0 또는 1)를 출력한다.
    b. 하나라도 다른 원소가 있다면, 4개의 분할 영역으로 나눈다.
3. 각 분할된 영역에 대해 재귀적으로 2번 과정을 반복한다.
4. 각 영역의 결과를 괄호로 묶어서 출력한다.

#### 쿼드 트리 문제 소스코드 예

import java.io.*;
import java.util.Scanner;

public class Main {
    static int[][] map;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        compress(0, 0, N);
        System.out.println(sb);
    }

    static void compress(int x, int y, int size) {
        if (isUniform(x, y, size)) {
            sb.append(map[x][y]);
            return;
        }

        int newSize = size / 2;
        sb.append('(');

        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                compress(x + i * newSize, y + j * newSize, newSize);
            }
        }

        sb.append(')');
    }

    static boolean isUniform(int x, int y, int size) {
        int value = map[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (map[i][j] != value) {
                    return false;
                }
            }
        }
        return true;
    }
}