분할 정복이란(Divide & Conquer)

분할 정복이란?

분할 정복은 문제를 2개 또는 그 이상의 작은 부분 문제로 나눈 다음 푸는 것(분할)으로

푼 다음에는 다시 합쳐서(정복) 정답을 구하는 알고리즘이다. 말 그대로 분할하고 정복하여 정답을 도출하는 알고리즘이다.

분할 정복 대표 알고리즘

• 퀵 소트 : 평균적으로 O(nlogn), 최악의 경우 O(n^2)의 시간복잡도를 가지는 알고리즘으로 평균적인 상황에서 최고의 성능을 자랑한다. 피벗을 하나 고른다음 그것보다 작은 것을 앞으로, 큰 것을 뒤로 보낸다. 그 다음 피벗의 앞과 뒤에서 퀵 정렬을 수행한다. https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
• 머지 소트 : O(nlogn)의 시간복잡도를 가지는 알고리즘으로 N개를 N/2, N/2 개로 나눈다. 왼쪽 N/2와, 오른쪽 N/2를 정렬하고 두 정렬한 결과를 하나로 합친다.  https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
• 퀵 셀렉트 : 정렬되지 않는 리스트에서 k번째 작은 수를 찾는 알고리즘으로 퀵 소트와 같지만 한쪽만 호출한다. 따라서 시간 복잡도가 O(n) 으로 줄어들지만 최악의 경우 O(n^2)이 걸리기도 한다.
• 큰 수 곱셈(카라추바 알고리즘) : 큰 수에 대해 효과적인 곱셈 알고리즘이다. https://ko.wikipedia.org/wiki/%EC%B9%B4%EB%9D%BC%EC%B6%94%EB%B0%94_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• 이분탐색 : 정렬되어 있는 리스트에서 값을 찾는 알고리즘으로 O(nlogn)의 시간복잡도를 가진다. https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

DP와 차이점

다이나믹 프로그래밍도 문제를 작은 부분으로 나눈 다음 합쳐서 정답을 도출하는 알고리즘이다. 

그렇다면 분할 정복 알고리즘과 어떤 차이점이 있을까? 

바로 "작은 문제가 중복이 되는지의 여부에 대한 차이"이다.

다이나믹 프로그래밍은 작은 문제가 중복 되기때문에 이 부분을 기록해서 메모이제이션을 이용하여 중복을 제거한다.

분할 정복은 작은 문제가 중복 되지 않기 때문에 이 부분을 기록하지 않고 한번씩 도출하여 문제를 풀어 나간다.