분할 정복 알고리즘(Divide and Conquer Algorithm)은 주어진 문제를 작은 부분으로 나누고(divide) 각각을 해결한 후에 그 결과를 합쳐(conquer) 최종적인 해답을 찾아내는 알고리즘입니다. 이를 통해 전체 문제를 해결하는 것보다 작은 문제들을 해결하는 것이 더욱 효율적인 경우에 사용됩니다.

분할 정복 알고리즘의 주요 특징

• 분할(Divide)
  주어진 문제를 작은 부분으로 나눕니다. 이때 나누는 과정은 보통 문제의 크기를 절반으로 줄이는 것이 일반적입니다.

• 정복(Conquer)
  작은 부분 문제를 재귀적으로 해결합니다. 이때 작은 문제들이 충분히 작아서 직접적인 해답을 구
  할 수 있어야 합니다.

• 합병(Combine)
  작은 문제들의 해답을 합쳐서 전체 문제의 해답을 찾아냅니다.

분할 정복 알고리즘이 대표적으로 사용되는 문제

• 병합 정렬(Merge Sort)
  배열을 절반으로 나눈 뒤 각각을 정렬하고 합병하여 정렬된 배열을 만듭니다.

• 퀵 정렬(Quick Sort)
  피벗을 기준으로 배열을 두 부분으로 나눈 뒤 각각을 정렬합니다.

• 이진 검색(Binary Search)
  정렬된 배열에서 특정 값을 찾는 알고리즘으로, 배열을 반으로 나누어 탐색합니다.

분할 정복 예시 - 최댓값 찾기

public class Main {

    public static int getMax(int[] arr, int left, int right) {
        int m = (left + right) / 2;
        if(left == right){
            return arr[left];
        }

        left = getMax(arr, left, m);
        right = getMax(arr, m + 1, right);

        return (left > right) ? left : right;
    }


    public static void main(String[] args) {
        int arr[] = {6, 2, 9, 8, 1, 4, 17, 5};
        System.out.println(getMax(arr, 0, arr.length - 1));
    }
}

분할 정복 알고리즘은 문제를 해결하는 방법이 직관적이고 간단하며, 재귀적인 구조를 가지고 있어 이해하기 쉽습니다. 또한 많은 문제들에 적용 가능하며, 특히 큰 문제를 작은 부분으로 나누어 해결하는 데에 효과적입니다.