부분 문제에 대한 각개 격파
첫 챕터 Brute force에서는 재귀 호출을 통해 큰 문제를 수 많은 작은 조각들로 나누어 하나씩 문제를 해결하는 방식으로 접근했다.
분할 정복 역시 이와 유사한 개념을 사용하지만, 큰 문제를 작은 문제들로 바로 쪼개는 것이 아니라 비슷한 크기의 문제들로 점점 쪼개 나가는 방식으로 문제를 해결한다는 점에서 차이가 있다.
분할 정복이라는 이름에서 알 수 있듯이 이 방식은 문재를 작은 조각으로 점차 분할해 나가고 밑에서부터 병합하면서 올라오는 방식으로 처음의 문제를 해결해 나가는 접근법이다.
예시
병합 정렬
선택 정렬과 버블 정렬과 같은 직관적인 방식의 정렬은 n^2의 시간이 소요되는데, 분할 정복을 활용한 병합 정렬과 퀵 정렬은 평균적으로 n*log n 의 시간이 소요되어 훨씬 효율적으로 정렬을 수행할 수 있다.
병합 정렬과 퀵 정렬은 쪼개기 위한 기준을 설정하는 방식이 다를 뿐이지 분할 정복을 활용한다는 점에서 본질적으로 매우 유사한 정렬 알고리즘이다.
시간 복잡도가 n과 log n의 곱인 이유는 n만큼의 수를 절반으로 자른 단계의 수는 log n개, 각 단계마다 병합하는 데 드는 시간이 n이기 때문이다.
카라츠바 알고리즘
일반적인 곱셈 알고리즘은 이중 for문이 필요하기 때문에 n^2의 시간이 든다. 카라츠바 알고리즘은 분할 정복을 활용한 더 효율적인 곱셈 알고리즘이다.
a = a'x10^n + a''
b = b'x10^n + b''
이렇게 각 수를 두 부분으로 나누게 되면 두 수의 곱은
z2= a'' b''
z0= a' b;
z1 = (a'+a'') * (b'+b'') - z0 -z2
한 번의 곱셈으로 이루어진 세 수를 이용해 만들어질 수 있다는 데서 착안한 알고리즘이다.
카라츠바 알고리즘은 단순한 분할 정복 알고리즘과는 다르게 주어진 입력을 절반으로 쪼개고 두번의 재귀 호출을 하는 것이 아니라 세 번의 재귀 호출을 하기 때문에 시간복잡도를 계산하는 데 조금더 복잡한 사고가 필요하다.
