[알고리즘] 분할정복 알고리즘이란?

분할 정복 알고리즘

분할 정복(Divide and Conquer) 알고리즘은 문제를 더이상 나눠지지 않을 때까지 나누어서 각각을 풀면서 합병하여 문제의 답을 얻는 알고리즘이다. 알고리즘의 기법 중 하나다.

 

알고리즘 단계

분할 정복 알고리즘에는 크게 세가지 단계가 있다.

1. Devide : 문제가 분할이 가능한 경우, 2개 이상으로 나눈다.

2. Conquer : 나눈 문제가 여전히 분할이 가능하면 다시 Divide로 돌아가고, 분할이 안 되면 문제를 푼다. (재귀)

3. Combine : Conquer한 문제를 합쳐 원래의 정답을 찾는다.

 

분할 정복 알고리즘에는 재귀가 사용되므로 재귀 알고리즘의 문제점들을 그대로 갖고 간다.

 

문제 종류

• 이진 탐색(Binary Search)
• 정렬(퀵 정렬, 병합 정렬)
• 큰 숫자 곱하기(Karatsuba)
• 쉬트라쎈 행렬 곱셈 알고리즘
• Closest Pair of Points