분할정복법(Divide and Conquer)

1. 원래 문제를 풀 수 있을 정도의 작은 크기의 부분 문제들로 분할해 각각 해결한 후, 부분 문제의 해답을 잘 모아 원래 문제의 해답을 얻는 방법

   1. 크기가 작아질 뿐 문제 자체는 변하지 않기 때문에, 분할은 재귀적인 분할이 된다.
   2. 재귀적인 분할이므로 분할정복 방법의 알고리즘 수행시간 T(n)은 점화식으로 표현되는 것이 일반적이다.

2. 예1: n개의 수 중에서 최대 값 구하기 A: [3, 0, -5, 7, 2, -4, 6 9]

def find_max1(A):	
    if len(A) == 1: return A[0]
    else: return max(A[0], find_max1(A[1:]))

$T(n) = T(n-1) + c = O(n)$

def find_max2(A):	
    if len(A) < 1: return -infinity
    elif len(A) == 1: return A[0]	
    else: return max(A[:len(A)//2], A[len(A)//2:])

$T(n) = 2T(\frac{n}{2}) + c = O(n)$

$2^k = n$ -> $k = \log_2n, T(1) = c$

$T(n) = 2T(\frac{n}{2}) + c$
$T(n) = 2^2T(\frac{n}{2^2}) + 2c + c$

$\vdots$

$T(n) = 2^kT(\frac{n}{2^k}) + c(1 + 2 + ... +$ 2^(k-1) )

$T(n) = c(1 + 2 + ... + 2^k)$
$= \frac{1*(2^(k+1) -1 )}{2-1} = c(2n-1)$
$= O(n)$

그림으로 풀기

$T(n) = c(1 + 2 + ... + 2^k)$
$= \frac{1*(2^(k+1) -1 )}{2-1} = c(2n-1)$
$= O(n)$

3. 예2: $a^n$을 계산하기(n을 양의 정수로 가정)

def power1(a, n): # 선형 재귀 호출로 작성하기
	if n == 1: 
return a
	return a * power1(a, n-1)

수행시간 점화식: T(n) = T(n-1) + c = O(n)

def power2(a, n): # 이중 재귀 호출로 작성하기
	if n == 0: return 1
	if n%2 == 1: # n 홀수
		return power2(a, n//2)*power(a, n//2)*a
	else: # n 짝수
		return power2(a, n//2)*power(a, n//2)

수행시간 점화식: T(n) = 2T(n/2) + c = O(n)

power(a, n//2)를 이미 구했는데 여러번 호출하는 것은 비효율적!
변수 p에 저장해놓고 재사용하자!

def power3(a, n): # 선형 재귀 호출이지만, 빠른 방법
	if n == 0: return 1
	p = power2(a, n//2)
	if n%2 == 1: # n 홀수
		return p * p * a
	else: # n 짝수
		return p * p

수행시간 점화식: T(n) = T(n/2) + c = O(log n)

$2^k = n$ -> $k = \log_2 n$
$T(n) = T(\frac{n}{2}) + c$
$=T(\frac{n}{2^2}) + c + c$

$\vdots$

$=T(\frac{n}{2^k}) + k*c$
$c(k+1) = O(\log n)$