분할정복

분할 정복이란 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 계산하고 이를 병합해 문제를 해결하는 기법이다. 문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제들로 나누고(Divide) 문제를 해결한 다음(Conquer) 그 결과를 이용해 다시 전체 문제를 해결하며 합치는 방법이다. 관련 알고리즘 분할 정복 방식으로 해결되는 문제로 다음 알고리즘이 있습니다. 정렬 문제(퀵 정렬, 병합 정렬) 큰 숫자 곱하기(Karatsuba 알고리즘) : n자리 수 2개를 곱하여 결과를 나타내는 알고리즘 이진 탐색 (Binary Search) Closet Pair of Points 문제 : 모든 point 쌍의 거리 중 최소의 거리를 찾는 문제 Strassens's 알고리즘 : 두 ..