Algorithm Analysis: Divide & Conquer

알고리즘 관련 모든 글은 연세대학교 안형찬 교수님의 CSI_3108: Algorithm Analysis의 강의 내용과 자료입니다.

이번 글에서는 알고리즘 풀이에서 많이 쓰이는 divide & conquer와 그 시간복잡도를 간단히 알게 해주는 Master Theorem을 살펴보도록 하겠습니다.

Divide & Conquer

크게 3가지 단계로 진행됩니다.

1. Divide : 한 문제를 같은 크기를 갖는 몇 개의 subproblem들로 나눕니다.
2. Conquer : 그리고 각각에 대해서 subproblem을 구합니다.
3. Combine: 각 subproblem들에 대해 합치거나 더 가공하여 최종 답을 냅니다.
   

Integer Multiplication

Given two n-bit positive integers x and y, calculate their product.

문제가 매우 간단합니다. 두 정수가 주어졌을 때 곱하라는 내용입니다. 이런 뜬금없는 문제가 왜 나오는지 의아할 수 있습니다. 우리는 대부분 곱셈을 $O(1)$만에 하기 때문입니다. 하지만 이런 알고리즘이 어떨 때 필요하냐면 굉장히 큰 수끼리 곱하는 경우에 필요합니다. 너무 커서 $O(1)$만에 할 수 없는 수준일 때를 말합니다. 이런 n비트짜리 큰 두 수를 곱할 때 우리는 divide & conquer 방식을 취할 수 있습니다. 우선 자연스럽게 n-bit짜리 X와 Y를 2개로 쪼개보겠습니다.

이를 그림으로 표현하면 이렇습니다.

그리고 x와 y를 곱하면 이런 식이 완성됩니다.

그렇다면 우리가 $x$를 각각 $x_1,x_0$으로 나누고 $y$를 각각 $y_1,y_0$으로 나누었습니다. 이를 각각 하나의 subproblem으로 볼 수 있습니다. 그렇게 알고리즘으로 나타내보겠습니다.

1차 시도

function Multiply(x,y)
	if n<=3:
		do the elementary math (counting stones)
	p_1=Multiply(x_1,y_1)
	p_2=Multiply(x_0,y_1)
	p_3=Multiply(x_1,y_0)
	p_4=Multiply(x_0,y_0)
	
	sol=p_1*2^{2*(n/2)}+(p_2+p_3)*2^{n/2}+p_4
	
	return sol

각각 쪼갠 subproblem들로 구해서 답을 내게 됩니다. 위에서 말한 elementary math는 아마 우리가 초등학교에서 심지어 구구단조차 배우지 않은 상태에서 곱셈이라는 것을 처음 배울 때 쓰는 방법입니다.

우리가 이제는 너무나 곱셈을 잘해서 이 알고리즘이 잘 안 보입니다. 하지만 잘 생각해보면 놀랍게도 우리는 초등학교 때부터 for문을 돌리고 있었습니다! 코드로 표현하면 이렇습니다.

result=0

for i = 1, ... , p:
	for j = 1, ... , q:
		result=result+1

그렇습니다. 우리는 초등학교 때부터 이중 for문을 돌리고 있었습니다. 이제 다시 본론으로 돌아와 우리가 짠 알고리즘의 시간 복잡도를 계산해보겠습니다. 결론부터 이야기하면 시간복잡도는 $\Theta(n^2)$입니다. Divide & conquer 방식의 알고리즘은 시간복잡도 계산을 매우 편리하게 해주는 theorem이 존재합니다. 바로 $Master\,\,theorem$이라고 불리는 theorem입니다.

Master theorem

단순히 아래 식에 parameter인 $a,b,f(n)$의 시간복잡도만 넣어주면 Divide & conquer의 시간 복잡도가 뚝딱 계산되어 나오는 편리한 정리입니다.

• $a$ : divided & conquer 에서 몇 개의 subproblem으로 나누는지, 한 레벨에서 재귀가 몇 번 불리는지
• $b$ : subproblem에 들어가는 input 사이즈가 기존 input 대비 줄어드는 비율의 역수
  • 예시: 만약 subproblem의 input 사이즈가 2/3 으로 줄어드는 알고리즘이라면 $b$는 3/2가 됩니다
• $f(n)$ : subproblem들을 combine하는 merging step에 드는 시간복잡도
  • 예시: $a=2, b=2,f(n)=O(n)$일 때는 $log_22=1$인데, $\epsilon$ 은 0이 아닌 양수이므로 $n^1$을 만들 수 없습니다. 따라서 2번의 경우에서 $k=0$인 경우라고 할 수 있습니다.

이를 지금 문제에 적용해보면 우리는 위에서 하나의 Multiply(x,y)가 4개의 Multiply()를 호출합니다. 그리고 각 subproblem은 원래의 problem보다 크기가 1/2 줄어든 input을 받게 됩니다. 그러므로 $a = 4,\,\,b=2$ 입니다. 그리고 마지막 merging step에서는 2를 곱한다는 것은 bit를 앞쪽으로 한칸씩 미는 것입니다. 그러므로 merging step은 linear time $O(n)$에 가능합니다. 이에 따라 우리는 1번 케이스를 적용합니다. $T(n)=\Theta (n^{log_2 4})$가 되어 우리가 아까 봤던 $\Theta(n^2)$의 시간복잡도가 나옵니다. 이렇듯 master theorem에 특정 값들을 넣어주면 시간복잡도는 매우 편하게 계산할 수 있습니다. 덧붙여 말하자면 어차피 elementary math부분은 n이 3이하일 때 돌아가므로 n에 구속되지 않는 상수로 볼 수 있습니다.

여기서 끝낼 수도 있지만 사실 우리는 더 좋은 알고리즘을 만들 여지가 남아있습니다. 아래와 같은 이유 때문입니다.

이렇기 때문에 굳이 p_2=Multiply(x_0,y_1) p_3=Multiply(x_1,y_0) 를 추가적으로 부를 필요가 없습니다. 왜냐하면 이미 갖고 있는 애들로 조합을 하면 되기 때문입니다. 그래서 이를 이용해서 더 나은 알고리즘을 만듭니다.

2차 시도

function Multiply(x,y)
	if n<=3:
		do the elementary math (counting stones)
	p_1=Multiply(x_1+x_0,y_1+y_0)
	p_2=Multiply(x_1,y_1)
	p_3=Multiply(x_0,y_0)
	
	sol=p_2*2^{2*(n/2)}+(p_1-p_2-p_3)*2^{n/2}+p_3
	
	return sol

이렇게 Multiply() 호출 횟수가 줄었습니다. 그래서 다시 시간복잡도를 계산하기 위해 master theorem을 이용하면, $a = 3,\,\,b =2$ 가 되어 총 시간복잡도는 $\Theta(n^{log_2 3})$ 입니다.

정리

Divide & conquer에서는 배타적인 subproblem들로 문제를 나누어 각각에서 해답을 구하고 그것을 최종 답을 내는 데에 이용합니다. subproblem들이 나뉘어지는 그 경계선에 optimal solution이 걸쳐있는 경우가 존재할 때 merging(combining) step에서 이를 고려하여야 합니다. Divide & conquer에서는 이런 사실을 간과하기 쉬우므로 늘 조심해야 합니다.

Algorithm Analysis