[알고리즘] 분할 정복 (Divide and Conquer)

💡 분할 정복 (Divide and Conquer)

👉 큰 문제를 작은 부분 문제로 나누어 해결하는 방법이다.

• 합병 정렬 : 배열을 1개 단위까지 쪼개서 서로 정렬하면서 모아가는 방법
• 퀵 정렬 : pivot을 기준으로 좌우 형태로 재귀 호출을 하며 잘게 나누고 합치면서 정렬하는 방법
• 이진 검색 : 중앙 값을 뽑아서 좌측인지 우측인지 비교하면서 정렬하는 방법
• 등등

👉 분할 정복 과정

1. 문제를 하나 이상의 작은 부분들로 분할한다.
2. 부분들을 각각 정복한다.
3. 부분들의 해답을 통합하여 원래 문제의 답을 구한다.

---

💡 분할 정복의 장단점

👉 장점

• 문제를 나누어 처리하여 어려운 문제를 해결할 수 있다.
• 병렬처리에 이점이 있다.

👉 단점

• 재귀 호출 구조이기 때문에 메모리를 많이 사용한다.

---

💡 분할 정복 예시

👉 최대 값 찾기

• 배열 : [3, 5, 10, 50, 25, 30, 1, 15]

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