이번 포스팅에서는 문제를 해결하기 쉽도록 여러 작은 부분으로 나눈 후에 각각 해결하고, 해결된 답안들을 한데 모아서 문제를 해결하는 분할정복법에 대해서 알아보도록 하겠습니다!
목차
0. 분할정복 - 이분탐색
분할정복은 분할 - 정복 - 통합 순으로 진행되는 전형적인 하향식(top-down) 접근방법입니다.
무슨 말인지 파악하기 위해 재귀적 방식으로 만든 간단한 이분탐색을 가져왔습니다.
이분탐색을 분할, 정복, 통합으로 나눠보면 아래와 같습니다.
분할 : 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택하고, 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택합니다.
정복 : 선택된 반쪽 배열에서 x를 찾습니다.
통합 : X
# 찾는 item의 index를 호출
def location(data, item, low, high):
if low > high:
return -1
else:
mid = (low+high)//2
if x == data[mid]:
return mid
elif x < data[mid]:
return location(low, mid-1)
else:
return location(mid+1, high)
data = [1,3,5,6,7,9,10,14,17,19]
n = 10
location = bs(data,17,0,n-1)
print(location)
이걸 최악의 경우에 대해 시간복잡도를 분석해보면, 매번 검색하는 반쪽 배열의 크기가 정확하게 n/2가 되는 경우에는
W(1) = 1
W(2) = W(1) + 1 = 2
W(4) = W(2) + 1 = 3
W(8) = W(4) + 1 = 4
...
W(2^k) = k + 1
...
W(n) = log_n + 1
이렇게 W(n)을 구할 수 있습니다.
일반적인 경우(정확하게 반쪽이 안나는 경우)는 반쪽 배열은 floor(n/2)가 됩니다.
이 부분은 수학적 귀납법으로 해결할 수 있는데, 아래 사진으로 갈음합니다.
1. 분할정복 - 합병정렬
이번엔 합병정렬을 살펴보겠습니다.
반으로 계속 쪼개다가 더 이상 쪼갤 수 없을 때 뭉치면서 정렬을 하는 방식으로 구할 수 있습니다.
사진으로 보면 더욱 명확히 분할과 합병의 모습을 보실 수 있습니다.
# 합병정렬 1
- 최악의 경우 시간복잡도 : W(h,m) = W(h) + W(m) + h + m - 1이고
- W(h)는 U를 정렬하는데 걸리는 시간, W(m)은 V를 정렬하는 데 걸리는 시간,
- h + m - 1은 합병하는데 걸리는 시간이다.
- 정수 n을 2^k, (k≥1 이라고 가정)이라고 하면 h = n/2, m = n/2가 되고,
- 최악의 경우 재현식은 W(n) = 2W(n/2)+n-1 (n>1) 이고, n=2^k(k≥1), W(1) = 0
- 이 재현식의 해는 도사정리의 2번을 적용하면 W(n)∈Θ(nlogn)임을 알 수 있다.
- 공간복잡도는 2n
maxStorage = nowStorage = 0 # 현재 사용중인 추가 저장공간의 양을 저장하는 전역변수
def mergeSort(n, s):
global maxStorage, nowStorage
h = n//2
m = n-h
u = []
v = []
if (n > 1):
u = s[:h]
v = s[h:n]
nowStorage += h+m # 사용과정
if maxStorage < nowStorage:
maxStorage = nowStorage
mergeSort(h,u)
mergeSort(m,v)
merge(h,m,u,v,s)
def merge(h,m,u,v,s):
global maxStorage, nowStorage
i = j = k = 0
while i < h and j < m:
if u[i] < v[j]:
s[k] = u[i]
i += 1
else:
s[k] = v[j]
j += 1
k += 1
if i == h:
s[k:h+m] = v[j:m]
else:
s[k:h+m] = u[i:h]
nowStorage -= h+m # 반납과정
s=[3,16,13,1,9,2,7,5,8,4,11,6,15,14,10,12]
print("원본 데이터 :", s)
mergeSort(16,s)
print("mergeSort 사용시 추가적인 저장공간 :", maxStorage)
print("정렬된 데이터 :", s)
print()
이번에는 공간복잡도를 n으로 줄인 식입니다. 특정 단계에서 사용된 공간을 재활용 하는 방법으로 공간복잡도를 절반으로 줄였습니다.
# 합병정렬 2
maxStorage2 = nowStorage2 = 0 # 현재 사용중인 추가 저장공간의 양을 저장하는 전역변수
def mergeSort2(s, low, high):
global maxStorage2, nowStorage2
if low < high:
mid = (low+high)//2
mergeSort2(s, low, mid)
mergeSort2(s, mid+1, high)
merge2(s, low, mid, high)
def merge2(s, low, mid, high):
global maxStorage2, nowStorage2
i, j, k = low, mid+1, low
u = []
for temp in range(high+1):
u.append(0)
while i <= mid and j <= high:
if s[i] < s[j]:
u[k] = s[i]
i += 1
else:
u[k] = s[j]
j += 1
k += 1
if i == mid+1:
u[k:high+1] = s[j:high+1]
else:
u[k:high+1] = s[i:mid+1]
nowStorage2 += high+1 # 사용과정
if maxStorage2 < nowStorage2:
maxStorage2 = nowStorage2
s[low:high+1] = u[low:high+1]
nowStorage2 -= high+1 # 반납과정
s2=[3,16,13,1,9,2,7,5,8,4,11,6,15,14,10,12]
print("원본 데이터 :", s2)
mergeSort2(s2,0,15)
print("mergeSort2 사용시 추가적인 저장공간 :", maxStorage2)
print("정렬된 데이터 :", s2)
# 사용하는 Storage를 설정할 때 high+1만큼의 크기를 잡았기 때문에 슬라이드의 내용과 조금 다를 수 있지만
# 결과적으로 최대 n만큼의 추가공간을 사용하기 때문에 공간 사용량은 차이가 없다.
# 슬라이드 19의 알고리즘을 파이썬을 이용해 만들기 위해서는
# s와 u가 같은 위치에 들어가야 하는데, 앞쪽 인덱스를 초기화하지 않고는 뒷쪽 인덱스를 사용할 수 없어서 이런 식으로 만들게 되었다.2. 분할정복 - 빠른정렬
빠른정렬은 절대적으로 가장 빠른 정렬은 아닙니다. 하지만 당시에는 빨랐기 때문에(...) 이런 이름이 붙었습니다. 좀 더 현실적으로 이름을 붙이자면 분할교환정렬이라고 부르는게 더 정확하겠네요.
특정 기준을 잡아서 정렬을 합니다. 보다 깔끔한 이해를 위해서 아래 유튜브 영상을 준비했습니다. 참고하세요!
www.youtube.com/watch?v=cVMKXKoGu_Y
# 입력이 거꾸로로 정렬이 되어있다면 최악!
# 최악의 시간복잡도는 n(n-1)/2 -> O(n^2)
# 평균의 시간복잡도는 O(nlogn).. 풀이는 많이 길기 때문에 생략!
def quickSort(s, low, high):
global pivotpoint
if high > low:
partition(s,low,high)
quickSort(s,low,pivotpoint-1)
quickSort(s,pivotpoint+1,high)
def partition(s, low, high):
global pivotpoint
pivotitem = s[low]
i = low+1
j = low
while i <= high:
if s[i] < pivotitem:
j += 1
s[i], s[j] = s[j], s[i]
i += 1
pivotpoint = j
s[low], s[pivotpoint] = s[pivotpoint], s[low]
s = [3,5,2,9,10,14,4,8]
quickSort(s,0,7)
print(s)3. 분할정복 - 행렬 곱셈
이번엔 단순 행렬곱셈과 쉬트라센 행렬곱셈에 대해서 살펴보겠습니다.
이전 포스팅에서 했던 단순 행렬곱셈은 시간복잡도가 O(n^3)임을 확인하고 간단하게 넘어가고, 쉬트라센 행렬곱셈에 대해 자세히 알아보도록 하겠습니다.
# 시간복잡도는 O(n^3)
# 만약 2*2 행렬이라면 8번의 곱셈과 4번의 덧셈이 필요하다
def matrix_multiplication(a,b):
c = [[0 for i in range(len(b[0]))] for j in range(len(a))]
for i in range(len(a)):
for j in range(len(b[0])):
for k in range(len(a[0])):
c[i][j] = c[i][j] + a[i][k] * b[k][j]
return c
a=[[1,2],[3,4]]
b=[[4,1],[1,0]]
print(matrix_multiplication(a,b))
3.0. 분할정복 - 쉬트라쎈의 행렬곱셈
쉬트라센의 방법은 아래 위키를 보면 보다 자세히 알 수 있습니다.
ko.wikipedia.org/wiki/%EC%8A%88%ED%8A%B8%EB%9D%BC%EC%84%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
슈트라센 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 선형대수학에서 슈트라센 알고리즘은 독일의 수학자 폴커 슈트라센(Volker Strassen)이 1969년에 개발한 행렬 곱셈 알고리즘이다. 정의에 따라 n×n 크기의 두 행렬을
ko.wikipedia.org
기존 알고리즘이 O(n^3)의 시간이 소요됐다면, 이 알고리즘은 대략 O(n^2.807)의 시간이 소요됩니다. 적어보이지만, n이 커진다면 충분히 엄청난 차이를 보여주게 된다. 2*2 행렬을 7번의 곱셈과 18번의 덧셈으로 처리할 수 있습니다. 분명 위의 일반 곱셈에 비해 손해를 보는 것 같지만, 곱셈을 1번 덜 합니다.(!) 행렬이 커질수록 이 곱셈은 많은 시간이 걸리게 되므로 n이 크면 클수록 이 쉬트라센의 방식이 더 좋은 방식이 됩니다.
# numpy를 이용하여 보다 간결하게 만들었습니다.
from numpy import *
def strassen (n, A, B, C):
threshold = 2
A11 = array([[A[rows][cols] for cols in range(int(n/2))]for rows in range(int(n/2))])
A12 = array([[A[rows][cols] for cols in range(int(n/2),int(n))]for rows in range(int(n/2))])
A21 = array([[A[rows][cols] for cols in range(int(n/2))]for rows in range(int(n/2),int(n))])
A22 = array([[A[rows][cols] for cols in range(int(n/2),int(n))]for rows in range(int(n/2),int(n))])
B11 = array([[B[rows][cols] for cols in range(int(n/2))]for rows in range(int(n/2))])
B12 = array([[B[rows][cols] for cols in range(int(n/2),int(n))]for rows in range(int(n/2))])
B21 = array([[B[rows][cols] for cols in range(int(n/2))]for rows in range(int(n/2),int(n))])
B22 = array([[B[rows][cols] for cols in range(int(n/2),int(n))]for rows in range(int(n/2),int(n))])
# print(A11, A12, A21, A22, B11, B12, B21, B22)
if (n <= threshold):
C = array(A) @ array(B)
else:
M1 = M2 = M3 = M4 = M5 = M6 = M7 = array([])
M1=strassen(int(n/2), (A11 + A22), (B11 + B22), M1)
M2=strassen(int(n/2), (A21 + A22), B11, M2)
M3=strassen(int(n/2), A11, (B12 - B22), M3)
M4=strassen(int(n/2), A22, (B21 - B11), M4)
M5=strassen(int(n/2), (A11 + A12), B22, M5)
M6=strassen(int(n/2), (A21 - A11), (B11 + B12), M6)
M7=strassen(int(n/2), (A12 - A22), (B21 + B22), M7)
C = vstack([ hstack([M1+M4 -M5 + M7, M3 + M5]), hstack([M2 + M4, M1 - M2 + M3 + M6]) ])
return C
n = 4
#A = [[1 for cols in range(n)]for rows in range(n)]
#B = [[2 for cols in range(n)]for rows in range(n)]
A=[ [1,2,0,2], [3,1,0,0], [0,1,1,2],[2,0,2,0]]
B=[ [0,3,0,2], [1,1,4,0], [1,1,0,2],[0,5,2,0]]
C = array(A)@array(B)
D = [[0 for cols in range(n)]for rows in range(n)]
print(C)
D=strassen(n, A, B, D)
print(D)
4. 분할정복 - 큰 정수 곱셈
이번에는 큰 정수를 곱셈하는 알고리즘을 만들어봅시다.
파이썬에서는 사실 크게 의미가 없을 수 있지만, C++와 같은 언어에서는 메모리의 크기때문에 큰 정수의 연산을 하기 굉장히 어렵습니다. (이것에 대한 알고리즘 문제를 PS를 접한 초창기에 굉장히 많이 풀었습니다.. 브론즈문제인줄 알고...)
# 시간복잡도는 Θ(n^log4) = Θ(n^2) (곱셈 4번!)
def prod(a,b):
n = max(len(str(a)),len(str(b)))
if a == 0 or b == 0:
return 0
elif n <= 4: # threshold = 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 prod(x,w)*10**2*m+(prod(x,z)+prod(w,y))*10**m+prod(y,z)
a = 1234567812345678
b = 2345678923456789
print(prod2(a,b))
print(a*b)
# 시간복잡도 Θ(n^log3) ~= Θ(n^1.58) (곱셈 3번!!)
def prod2(a,b):
n = max(len(str(a)),len(str(b)))
if a == 0 or b == 0:
return 0
elif n <= 4: # threshold = 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 = prod2(x+y,w+z)
p = prod2(x,w)
q = prod2(y,z)
return p*10**(2*m) + (r-p-q)*10**m + q
a = 1234567812345678
b = 2345678923456789
print(prod2(a,b))
print(a*b)5. 도사 정리(The Master Theorem)
위에서 도사정리라는 말이 나와서 그게 뭐지 하고 넘어갔을 수 있어서 마지막에 정리해서 넣어뒀습니다!
도사정리란 시간복잡도가 얼마인지 감이 잘 안 오는 친구들의 시간복잡도를 구할 때 유용하게 사용할 수 있는 방법입니다.
아래 사진으로 올려놓았지만, 보다 직관적으로 적어놓으면 아래 글과 같습니다.
0. g(n)이 더 무거우면 g(n)이 수행 시간을 결정!
1. f(n)이 더 무거우면 f(n)이 수행 시간을 결정!
2. g(n)과 f(n)이 같은 차수면 g(n)에 logn을 곱한 것이 수행 시간!
위 내용을 파악하고 T(n) = a * T(n/b) + f(n)을 기억한 후에 대입만 해주면 절반 이상은 끝난 겁니다!
그 후 g(n)과 f(n)을 비교해줘서 g(n)이 더 큰지 f(n)이 더 큰지 확인 후에 위의 조건 3개와 맞춰보면 끝!
추가로 f(n)이 더 큰 경우, c>=1이라면 도사보조정리를 사용해야합니다.
도사보조정리는 아래쪽에 추가로 올리겠습니다!
추가로 도사보조정리도 올립니다!
f(n)이 더 무겁고, c>=1인 상황일 때 사용하시면 됩니다!
최근댓글