분할정복법(Divide & Conquer)에 대하여
: 분할정복법은 사실 거창한 이론은 아니고, 여태까지 공부했던 합병정렬, 퀵정렬을 구현할 때도 사용했던 일종의 방법론이다. 알고리즘을 설계하는 데에 있어서 문제를 몇개의 부분으로 나누고(Divide), 나눈 부분을 각각 정복하고, 그 정복한(해결한) 부분을 합쳐서 최종적으로 문제를 해결하는 방법이다. 예를 들어, 합병정렬은 일반적인 선택정렬, 삽입정렬, 버블정렬이 O(N2)의 시간복잡도를 지니기에 그러한 문제를 해결하기위해 리스트를 두 부분으로 나눠서 각각의 리스트를 정렬하고, 그 정렬한 리스트를 바탕으로 최종목표(리스트 정렬)를 해결한다. 결과적으로 분할정복법은 대부분(거의 100%) 재귀호출을 통해 해결한다. 이유는 여태까지 재귀함수를 쓰면서 느꼈지만, 재귀함수 자체가 function(n-1)이 이미 제기능을 한다는 전제로 function(n)을 쓰는 형태(수학적 귀납법)이고, 재귀함수의 call stack에 쌓이는 함수들 하나하나가 결국 계속해서 분할정복법을 쓰는 함수이기 때문이다. 그럼 실제로 재귀호출, 분할정복법 등이 어떻게 코드상으로 표현되는지 예제를 통해 공부해보고자 한다.
- 위의 문제는 한번쯤은 풀어봤을 법한 연속해서 선택할 때 최대값이 몇인가에 대한 문제이다.
- 이를 먼저, 완전탐색법으로 풀어보면 다음과 같다.
max = l[0]
for i in range(1, n+1):
for j in range(0, n-i+1):
std = sum(l[i:i+j])
if std > max :
max = std
else:
continue
print(max)
-
위의 풀이는 아주 직관적이나, n2의 시간복잡도를 가지기에 좀더 효율적인 알고리즘을 찾아봐야한다.(조건의 n이 100,000이므로 10,000,000,000의 시행은 시간을 초과하기에)
-
그러면 이를 분할정복법 그리고 재귀함수를 이용해 풀어보자
def get_biggest(n) : if len(n) == 1: return n[0] else: mid = (0 + len(n)-1)//2 left = get_biggest(n[0:mid+1]) right = get_biggest(n[mid+1:]) l_idx = mid r_idx = mid+1 center_left = n[mid] center_right = n[mid+1] c_l_max = n[mid] c_r_max = n[mid+1] while True: if center_left>c_l_max: c_l_max = center_left if l_idx == 0 : break l_idx -= 1 center_left += n[l_idx] while True: if center_right>c_r_max: c_r_max = center_right if r_idx == len(n)-1 : break r_idx += 1 center_right += n[r_idx] center = c_r_max + c_l_max result = max([left,center,right]) return result print(get_biggest(l)) -
뭔가 while문을 여러개 써서.. 오히려 더 효율성이 떨어질 것 같지만, 실제로 이 함수의 시간복잡도는 O(nlogn)이다. 그럼 어떤 분할정복(?)을 한 것일까를 생각해보면, 먼저, 기본적으로 왼쪽(인덱스0)부터 연속값의 최대합을 구해보고(대신 중간 인덱스까지만), 오른쪽 끝부분부터 중간 인덱스까지의 최대합을 구해본다. 그 다음에 정가운데 인덱스부터 양끝으로 나아가면서 최대값을 구해보고 왼쪽으로 나아갔을 때의 최대값, 오른쪽으로 나아갔을 때의 최대값을 더한 것이 중간에서부터 구한 최대값이 된다(왼쪽, 오른쪽 두 부분을 같이 고려한 케이스). 그래서 결국 하나의 리스트를 3부분으로 나눠서(왼쪽, 오른쪽, 중간) 각각의 연속되는 최대값을 구하고, 그 셋중에 가장 큰 값이 최대값이 된다. 근데 이게 어떻게 O(nlogn)이 될까???..
-
이는 합병정렬과 시간복잡도를 구하는 점화식이 똑같은데, 왼쪽, 오른쪽을 구하는 시간복잡도를 각각 임의로 T(n//2)라고 해보자. 즉, n개의 요소로된 리스트에서 n//2개씩 들어있는 리스트 두개로 나누고, 각각의 연속된 최대값을 구할 때 T(n//2)가 걸린다고 할 수 있다(그러면, 전체 시간복잡도가 T(n)일 것). 여기서 재귀호출 개념을 써보면, T(n//2)는 결국 다시 위와 똑같은 과정을 거쳐서 연속된 수의 최대값을 구할 것이다. 즉, T(n//2)의 시간복잡도를 가지는 왼쪽 리스트의 시행에서도 그 리스트를 두부분으로 나눠서 이번엔 각각 T(n//4) + T(n//4) = 2T(n//4)의 시간복잡도가 될 것이다. 추가로, 여기에 마지막 작업인 가운데부터 양옆으로 연속된 최대값을 찾는 로직이 필요하므로 O(n)의 시간복잡도가 추가된다. 그러면 결국
'T(n) = 2*T(n//2) + O(n)'이 성립되게 되고(점화식), 결국 T(n)은 2분할을 몇번해야 하는가의 문제가 되기에 2분할의 회수에 따라 시간복잡도가 결정되게 되고 이는 O(nlogn)으로 표현할 수 있다. 이 때, O(n) < O(nlogn)이므로 결국 시간복잡도는 O(nlogn)이 된다. -
사실 재귀호출로 로직을 짜는건, 이전 함수가 제대로 작동할 것이라는 '가정'을 품고 함수를 짜는 것이기에 오히려 로직이 간단하다. 이전 함수가 제대로 리턴을 한다는 전제를 가지고 함수를 짜면 그 다음 값인 function(n)을 짜는게 훨씬 쉬워지기 때문이다.
합병정렬 복습
def merge_sort(l):
if len(l)==1 or len(l)==0:
return l
else:
mid = (0+len(l)-1)//2
left = merge_sort(l[0:mid+1])
right = merge_sort(l[mid+1:])
idx = 0
result = []
while True:
if left[0]>right[0]:
result.append(right[0])
right.pop(0)
if len(right) == 0:
result += left
break
else:
result.append(left[0])
left.pop(0)
if len(left) == 0:
result += right
break
return result
print(" ".join(list(map(str,merge_sort(l)))))
마무리
: 분할정복법은 에라토스테네스의 체나 모듈러 연산처럼 뭔가 이해하고, 외우는 지식이라기보다는 스킬적인 측면에 가까운 것 같다. 접근을 할 때 완전탐색법으로의 접근이 막혔다면, 다른 접근법으로 생각해볼만한 것으로 '분할정복법'이 있는 이런식인 것 같다. '문제를 여러개로 나누고, 그 각각의 문제를 해결한 것을 바탕으로 전체문제를 해결한다는 점 === 재귀함수의 로직' 이부분이 포인트인 것 같다.
