Divide & Conquer 분할 정복

: 큰 문제를 나누어서 풀고, 그 결과를 조합해서 문제를 해결하는 알고리즘 기법.

- 분할 (Divide) : 해결할 문제를 여러개의 작은 문제로 나눈다.

- 정복 (Conquer) : 작은 단위의 문제를 해결한다.

- 조합 (Merge or Combine) : 해결한 작은 단위 문제들을 합해 원래 문제의 답을 구한다.

 

1. 하노이의 탑

: 세 개의 기둥과 기둥에 꽂을 수 있는 서로 다른 크기의 원반이 있다. 전부 하나의 기둥에 큰 것이 아래에 있도록 꽂혀있다. 

- 한 번에 하나의 원반만 옮길 수 있다.

- 가장 위의 원반만 옮길 수 있다.

- 큰 원반이 작은 원반 위에 놓여서는 안된다. 

- 위의 규칙을 지키면서 하나의 기둥에서 다른 기둥으로 모든 원반을 옮긴다면?

 

1) 원반이 두 개인 경우 : 3회 

 

2) 원반이 세 개인 경우 : 7회 = 2*3 + 1

 

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 하노이 탑 이동 순서 골드5
public class boj11729 {
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        // 1. 첫번째 장대에 쌓인 원판의 개수 N
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // 출력 1. 옮긴 횟수 K
        sb.append((int) (Math.pow(2, N) - 1)).append("\n");

        // 2. 수행 과정 출력 가장 위의 원판을 어디로 옮기는지
        hanoiTop(N, 1, 3, 2);
        System.out.println(sb);
    }

    public static void hanoiTop(
            //하노이의 탑의 높이
            int height,
            // 현재 출발하고자 하는 기둥
            int start,
            // 목표로 하는 기둥
            int end,
            // 제3의 기둥
            int other
    ) {
        // 높이가 1이라면 start -> end로 이동시킨다.
        if (height == 1) {
            sb.append(start).append(" ").append(end).append("\n");
        }
        // 높이가 2이상이면 ?
        else {
            // 1. 한단계 아래 높이의 원반들을 other로 이동
            hanoiTop(height - 1, start, other, end);
            // 2. 제일 아래 원반을 end로 이동
            sb.append(start).append(" ").append(end).append("\n");
            // 3. other에 이동된 한단계 아래 높이의 원반들을 end로 이동.
            hanoiTop(height-1, other, end, start);
        }
    }
}

 

2. 병합 정렬

: 정렬되지 않은 배열이 있을 때

- 배열을 두개의 동일한 크기의 배열로 나눈다.

- 각 배열에 원소가 하나가 남을 때까지 반복한다.

- 나눠진 배열을 2개씩 정렬하면서 하나의 배열로 병합한다. 

public class MergeSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        mergeSort(arr, 0, arr.length-1);
    }

    // 정렬을 위해 나누는 단계
    private static void mergeSort(
            int[] arr,
            //정렬 대상 시작점
            int left,
            // 정렬대상 끝점
            int right
    ) {
        // left == right라면 나눠진 배열의 크기가 1이 된다.
        if (left < right) {
            //가운데 index를 찾는다
            int mid = left+(right-left)/2;
            // 반으로 나눠서 재귀호출한다
            mergeSort(arr, left, mid);
            mergeSort(arr, mid+1, right);

            //나눠진 배열을 합친다.
            merge(arr, left, right, mid);
        }
    }

    // 나누어진 배열을 합치는 단계
    private static void merge(
            int[] arr,
            int left,
            int right,
            // 합치는 배열이 어디서 나눠지는지 알기 위한 mid
            int mid
    ) {
        // 각 배열은 arr[left:mid], arr[mid+1:right]
        // 각 배열의 크기를 구한다 - 각 배열의 끝에 도달했음을 알기 위해서
        int n1 = mid - left +1;
        int n2 = right - mid;

        // 각 배열의 크기만큼  복사한다
        int[] leftArr = Arrays.copyOfRange(arr, left, left + n1);
        int[] rightArr = Arrays.copyOfRange(arr, mid + 1, mid + 1 + n2);

        // 반복문으로 각 배열의 제일 앞쪽부터 비교해가며 원본 배열에 덮어쓴다
        int i = 0; //왼쪽 배열 index
        int j = 0; //오른쪽 배열 index
        int k = left; // arr의 index
        while (i < n1 && j < n2) {
            //앞쪽 원소 중 왼쪽의 원소가 더 작거나 같을 경우,
            if (leftArr[i] <= rightArr[j]) {
                // 원본에 왼쪽 원소를 저장하고,
                arr[k] = leftArr[i];
                // 다음 원소로 넘어간다
                i++;
            } else { //오른쪽 원소의 경우
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // 왼쪽 배열이 끝나지 않았다면, 마저 저장한다
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        //오른쪽 배열이 끝나지 않았다면, 마저 저장한다
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = new int[]{25, 36, 18, 12, 15, 41, 29, 19};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

 

3. 퀵 정렬 (Quicksort)

: 병합 정렬과 같이 분할 정복 기법을 이용한 정렬 알고리즘

- 정렬되지 않은 배열이 있을 때, 

- 배열의 원소 중 하나를 Pivot으로 설정

- 배열의 원소들을 각각 Pivot과 비교 : 피봇보다 작은 원소는 왼쪽, 피봇보다 큰 원소는 오른쪽 

- 모든 원소를 다 검사하면 Pivot은 정렬된 위치에 위치한다.

- 이후 Pivot을 기준으로 왼쪽과 오른쪽을 나누어 반복한다.

 

public class QuickSort {
    public static void sort(int[] arr) {
        if (arr==null||arr.length<=1) return;
        quickSort(arr, 0, arr.length-1);
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // partition을 진행하고, pivot의 위치를 받는다.
            int pivotIndex = partition(arr, left, right);

            // 나는 배열을 각각 quicksort한다
            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        //오른쪽 끝을 pivot으로 설정한다
        int pivot = arr[right];
        // pivot보다 작은 원소를 어디로 할당할지를 결정하기 위한 index
        int i = left - 1;

        for (int j = left; j < right; j++) {
            //만약 현재 배열의 길이 pivot보다 작다면
            if (arr[j] <= pivot) {
                //이 원소가 위치해야 하는 곳을 조정하고
                i++;
                //현재 원소를 왼쪽으로 보낸다
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // pivot과 i+1의 위치를 바꾼다
        int temp = arr[i + 1];
        arr[i + 1] = arr[right];
        arr[right] = temp;

        return i+1;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{25, 36, 18, 12, 15, 41, 29, 19};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}