[알고리즘] 분할정복(Divide & Conquer)

<알고리즘 문제해결 전략>의 해당 단원 밑줄입니다.

"분할 정복을 사용하는 알고리즘들은 대개 세 가지의 구성 요소를 갖고 있습니다.

• 문제를 비슷한 크기의 더 작은 문제로 분할하는 과정(divide)

• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)

• 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)"

 

"같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다는 것을 보여주는 좋은 예입니다. 여러번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문입니다."

​​

 

---

병합 정렬 (Merge Sort)

수열을 가운데에서 쪼개 두 개의 부분수열로 만들고, 각 부분 수열에 대해서도 같은 절차를 재귀 호출한다. 기저 사례(base case)까지 쪼개 값이 반환되면, 대소를 비교하여 병합하며 수열을 정렬하게 된다.

​

 

 

퀵 정렬 (Merge Sort)

피봇(Pivot, 기준)을 정하고, 피봇과 대소를 비교해
수열을 [Pivot보다 작은 수들] [Pivot] [Pivot보다 큰 수들]의 꼴로 만든다.
이 때, 피봇의 위치는 정렬 후의 피봇의 위치와 일치하므로 [Pivot]을 제외하고 앞 뒤 묶음에 대해서 같은 절차를 각각 재귀호출 한다.

 

​

​

​

카라츠바의 빠른 곱셈 (Karatsuba)

$$a\left(256자리\ 자연수\right)\times b\left(256자리\ 자연수\right)\ =\ ?$$

$$a\ =a_1\left(a의\ 첫\ 128자리\right)\times 10^{128}+a_0\left(a의\ 그\ 다음\ 128자리\right)​$$

$$b\ =b_1\left(b의\ 첫\ 128자리\right)\times 10^{128}+b_0\left(b의\ 그\ 다음\ 128자리\right)​$$

$$\to \ a\times b=\left(a_1\times b_1\right)\times 10^{256}+\left(a_1\times b_0\ +\ a_0\times b_1\right)\ +\ \left(a_0\times b_0\right)​$$

 

a × b는 절반 크기의 4번의 곱셈으로 분할(divide)할 수있음을 알 수 있다.
그리고 다음과 같이 계산하면 4번의 곱셈을 3번의 곱셈으로 줄일 수가 있다.

 

$$z_0=\left(a_0\times b_0\right)$$

$$z_1=\left(a_1\times b_0\ +\ a_0\times b_1\right)\ ​$$

$$z_2=\left(a_1\times b_1\right)$$

$$※\ \left(a_1+b_0\ \right)\times \left(\ a_0+b_1\right)\ =$$

$$\left(a_1\times b_1\right)+\left(a_1\times b_0\ +\ a_0\times b_1\right)\ +\ \left(a_0\times b_0\right)$$

$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =z_0+z_1+z_2​​$$

 

아래 세 개의 변수를 적절히 연산(더하기, 시프트)하여 구한다.

 

z2 = a1 * b1;

z0 = a0 * b0;

z1 = (a0 + a1) * (b0 + b1) - z0 - z2;

​