[알고리즘] 분할 정복 알고리즘

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

주어진 문제의 입력을 분할하여 부분문제(subproblem)로 만들어 해결하는 방식

대부분 분할 정복 알고리즘은 단순 분할이 아닌, 분할된 부분문제들로 부분해를 찾아야 한다.

 

 

 

 

예시 문제로 크기가 n인 입력값이 있다고 가정하고
n을 3개로 분할한다 할때 각 부분문제의 크기가 $$n/2$$라고 하면
각 입력 크기의 반은 n/2라고 할수있다.


이제 입력 크기가 1이 되어 더 이상 분할할 수 없는 k번째까지 분할을 한다면,
$$n$$$$n/2$$$$n/2^2 (n/4)$$$$n/2^3 (n/8)$$$$n/n^4 (n/16)$$$$...$$$$n/2^k$$
위와 같은 순서가 성립된다.


이때, 입력크기가 1이되는 총 횟수를 k는 $$n/2^k$$이므로
$$n/2^k = 1$$$$k = log_2n$$
위 시간 복잡도가 성립된다.

 

 

---

 

 

분할 정복 알고리즘의 분류

 

분할 정복 알고리즘은 분할되는 "부분문제의 수 / 크기에 따라 분류"가 될 수 있다.

 

1. 문제가 k개로 분할되고, 부분문제 크기가 1/n으로 감소하는 알고리즘
   1. k = n = 2 (합병 정렬, 최근접 점의 쌍 찾기, 공제선 문제)
   2. k = 3, n = 2 (큰 정수의 곱셈)
   3. k = 4, n = 2 (큰 정수의 곱셈)
   4. k = 7, n = 2 (스트라센(Strassen)의 행렬 곱셈 알고리즘)
2. 문제가 2개로 분할되고, 부분문제 크기가 일정하지 않은 크기로 감소하는 알고리즘 (퀵 정렬)
   
3. 문제가 2개로 분할되나, 그중 1개 부분문제가 고려할 필요 없으며, 부분문제 크기가 1/2로 감소하는 알고리즘 (이진탐색)
   
   
4. 문제가 2개로 분할되나, 그중 1개가 고려할 필요가 없으며, 부분문제 크기가 일정치 않게 감소하는 알고리즘 (선택 문제 알고리즘)
   
   
5. 부분문제의 크기가 1, 2개씩 감소하는 알고리즘 (삽입 정렬, 피보나치수의 계산 등)

 

 

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

단순하며 비효율적 : 삽입, 선택, 버블

복잡하며 효율적 : 퀵, 힙, 합병, 기수