0.1 분할 정복 & 백트래킹

algorithm day11 분할 정복 & 백트래킹 0.1.1 분할 정복 설계 전략 분할 : 해결할 문제를 여러 개의 작은 부분으로 나눈다. 정복 : 나눈 작은 문제를 각각 해결한다. 통합 : 해결된 해답을 모은다. 분할 정복 기반의 알고리즘 # 거듭제곱 : O(logn) def recursive_power(x,n): if n == 1: return x if not n%2: # 짝수 y = recursive_power(x,n/2) return y*y else: # 홀수 y = recursive_power(x,(n-1)/2) 병합 정렬 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 외부 정렬의 기본이 되는 알고리즘 시간 복잡도 : O(nlogn) 과정 전체 자료 집합에 대해 최소 크기의 부분 집합이 될 때까지 분할 작업을 계속한다. 2 개의 부분 집합을 정렬하면서 하나의 집합으로 병합 알고리즘 # 분할 과정 # m : list def merge_sort...

원문링크 : 0.1 분할 정복 & 백트래킹