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

👩‍💻  분할 정복 이란?

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

ex) 합병 정렬, 퀵 정렬, 이진 검색 등

 

분할 정복의 과정은 아래와 같다.

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

 

✏️ 분할 정복의 장 단점

장점 : 

• 문제를 나누어 처리하며 어려운 문제 해결 가능
• 병렬 처리에 이점이 있음 (서로 영향을 끼치지 않고, 각각의 프로세싱을 돌릴 수 있는 구조)

단점:

• 메모리를 많이 사용(재귀 호출 구조)

 

✏️ 분할 정복 예시

계속 반으로 잘라가며 모두 분할이 되면 조건에 맞는 값을 찾고 재귀적으로 최종 답을 찾아간다.

public static int getMax(int[] arr, int left, int right){
	int mid = (left + rigth) / 2;
    if(left == right) return arr[left];
    
    left = getMax(arr, left, mid);
    right = getMax(arr, mid+1, right);
    
    return (left > right) ? left : right;
}