Divide and Conquer (분할 정복)

1. 분할 정복 (Divide and Conquer)

• 큰 문제를 작은 부분문제로 나누어 해결하는 방법
  • 합병 정렬, 퀵 정렬, 이진 탐색
• 분할 정복 과정
  • 문제를 하나 이상의 작은 부분들로 분할
  • 부분들을 각각 정복
  • 부분들의 해답을 통합하여 원래 문제의 답을 구함

2. 분할 정복의 장/단점

• 장점
  • 문제를 나누어 처리하며 어려운 문제 해결 가능
  • 병렬 처리에 이점이 있음
• 단점
  • 메모리를 많이 사용 (재귀 호출 구조)

3. 분할 정복 예시

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[] = {3, 5, 10, 50, 25, 30, 1, 5};
        System.out.println(getMax(arr, 0, arr.length - 1));
    }
}