1. 분할정복식 설계전략
분할 - 해결하기 쉽도록 문제를 여러개의 작은 부분으로 나눈다
정복 - 나눈 문제를 각각 해결한다
통합 - 필요하다면 해결된 해답을 모은다
하향식 (top-down) 접근방법
2. 이분 검색 : 재귀적 방식
문제 : 크기가 n인 정렬된 배열 S에 x가 있는가?
입력 : n, S[1,,,n], x
출력 : location, 만약 x가 없다면 -1
설계 전략 :
x가 배열의 중간에 위치하고 있는 항목과 같으면 끝
분할 : 배열을 반으로 나눈다. x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택, 그렇지 않으면 오른쪽에 위치한 반쪽
정복 : 선택된 반쪽 배열에서 x를 찾기
index location(index low, index high){
index mid;
if(low>high) return 0;
else{
mid=(low+high)/2
if(x==S[mid]) return mid;
else if(x<S[mid) return location(low,mid-1);
else return location(mid+1,high);
}
}3. 합병정렬
문제 : n개의 정수를 비내림차순으로 정렬
입력 : 정수 n, 크기가 n인 배열 S[1,,,n]
출력 : 비내림차순으로 정렬된 배열 S[1,,,n]
보기 : 27,10,12,20,25,13,15,22
분할 8
가운데를 잘라 4/4
다시 가운데를 잘라 2/2/2/2
다시 가운데를 잘라 1/1/1/1/1/1/1/1
정렬하며 합병 2/2/2/2
정렬하며 합병 4/4
합병 8
def mergeSort(low,high):
if high-low<2:
return;
mid=(low+high)//2
mergeSort(low,mid)
mergeSort(mid,high)
merge(low,mid,high)
def merge(low,mid,high):
i = low
j = mid
merged=[]
while i<mid and j<high:
if arr[i]<arr[j]:
merged.append(arr[i])
i+=1
else:
merged.append(arr[j])
j+=1
while i<mid :
merged.append(arr[i])
i+=1
while j<high:
merged.append(arr[j])
j+=1
for i in range(low,high):
arr[i]=merged[i-low]
arr=[27,10,12,20,25,13,15,22]
mergeSort(0,len(arr))
print(arr)
4. 퀵정렬
def quickSort(arr):
if len(arr)<=1: return arr
pivot = arr[len(arr)//2]
low,mid,end=[],[],[]
for i in arr:
if i<pivot:
low.append(i)
elif i==pivot:
mid.append(i)
else:
end.append(i)
return quickSort(low)+quickSort(mid)+quickSort(end)5. 행렬 곱셈
문제 : nn 크기의 행렬의 곱을 구하시오
입력 : 양수 n, nn 크기의 행렬 A와 B
출력 : 행렬 A와 B의 곱인 C
def matrix(n,arr1,arr2,arr3):
for i in range(0,n):
for j in range(0,n):
arr1[i][j]=0
for k in range(0,n):
arr1[i][j]=arr1[i][j]+(arr2[i][k]*arr3[k][j])
return arr1
슈트라센의 방법을 사용하는 것이 효율적
void strassen (int n, n*n_matrix A, n*n_matrix B, n*n_matrix&C){
if(n<=임계점)
단순한 알고리즘을 계산하여 C=A*B
else{
A를 4개의 부분행렬로 분할
B를 4개의 부분행렬로 분할
슈트라쎈의 방법을 사용하여 C=A*B
(strassen(n/2,A11+A12,B11+B22,M1)
}
}임계점 : 두 알고리즘의 효율성이 교차하는 문제의 크기
6. 큰 정수 계산법
예)
567,832 = 56710^3+832
u = x10^m+y
그래서 큰 정수 u,v를 곱하고 싶다면?
u = x10^m+y
v = w10^m+z
uv = (x10^m+y)(w10^m+z)
= xw10^2m+(xz+wy)10^m+yz
def calculation(a,b):
n=max(len(str(a)),len(str(b)))
if a==0 or b==0 : return 0;
elif n<=4: return a*b
else:
m=n//2
x=a//10**m
y=a%10**m
w=b//10**m
z=b%10**m
return (x*w)*(10**(2*m))+(x*z+w*y)*(10**m)+(y*z)
print(calculation(523546,123450))
print(523546*123450)
알고리즘의 개선 후
r = (x+y)*(w+z) = xw+(xz+yw)+yz
xz+yw = r-xw-yz
-> xw10^2m+(r-xw-yz)10^m+yz
def calculation(a,b):
n=max(len(str(a)),len(str(b)))
if a==0 or b==0 : return 0;
elif n<=4: return a*b
else:
m=n//2
x=a//10**m
y=a%10**m
w=b//10**m
z=b%10**m
r=calculation(x+y,w+z)
p=calculation(x,w)
q=calculation(y,z)
return p*10**(2*m)+(r-p-q)*10**m+q
print(calculation(523546,123450))
print(523546*123450)
7. 분할정복 사용하면 안되는 경우
(1) 크기가 n인 입력이 2개 이상의 조각으로 분할되며, 분할된 부분들의 크기가 거의 n에 가깝게 되는 경우
(2) 크기가 n인 입력이 거의 n개의 조각으로 분할되며 분할된 부분의 크기가 n/c인 경우
