Algorithm 03. 분할 정복

1. 분할 -> 정복 -> 통합

1. 분할(divide)
   • 문제를 여러개의 작은 부분 문제로 분할
2. 정복(conquer)
   • 부분 문제를 각각 해결
3. 통합(combine)
   • 필요 시 부분문제 해답을 모음

2. 거듭 제곱 문제

1. O(n)

def iterative_power(c, n):
    result = 1
    for _ in range(n):
    	result *= c
    return result

2. 분할정복 O(logn)

C^n 

• n 짝수 -> C^(n/2) * C(n/2)
• n 홀수 -> C^((n-1)/2) * C^((n-1)/2) * C

def recursive_power(c, n):
    if n == 1:
    	return c
    if n % 2 == 0:
    	y = recursive_power(c, n/2)
        return y*y
    else:
    	y = recursive_power(c, (n-1)//2)
        return y*y*c

 

3. 병합 정렬

• 전체 집합를 최소 단위의 부분집합까지 나눈다.
• 나눠진 부분집합을 정렬하면서 하나의 집합으로 병합한다.
• top-down 방식이며 시간복잡도는 O(nlogn)이다.

소스코드

def merge_sort(data):
    if len(data) <= 1: # 사이즈가 1보다 작을경우, 바로 리턴
   	    return data
    
    # 1. 분할(divide)
    mid = len(data)//2
    left = data[:mid]
    right = data[mid:]
    
    # 리스트의 크기가 1이 될 때까지 merge_sort재귀호출
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 2. 정복(conquer) -> 분할된 리스트 정렬하며 병합
    return merge(left, right)

def merge(left, right):
    result = [] # 두개의 분할된 리스트를 병합한 리스트
    
    while len(left) > 0 and len(right) > 0: # 두 분할 리스트에 원소가 있는 경우
    	# 두 분할 리스트의 원소를 비교하며 작은 것부터 result에 차례로 추가
        if left[0] <= right[0]: 
        	result.append(left.pop(0))
        else:
        	result.append(right.pop(0))
        
    if len(left) > 0: # left리스트에 원소가 남아있는 경우
    	result.extend(left)
    if len(right) > 0: # right리스트에 원소가 남아있는 경우
    	result.extend(right)
    
    return result

 

4. 퀵 정렬

소스코드

# data : 리스트
# start : 시작 인덱스
# end : 끝 인덱스
def quickSort(data, start, end):
    if start < end:
    	pivot = partition(data, start, end)
        quickSort(data, start, pivot-1)
        quickSort(data, pivot+1, end)
        

 

1. 호어 partition

• 피봇값보다 큰 값을 오른쪽, 작은값을 왼쪽 집합에 위치시킨다.

• 피봇을 두 집합의 가운데에 위치시킨다.

피봇의 위치는 정렬된 상태일 때, 자신의 위치에 놓인다.

피봇값은 다음 정렬 과정에서 제외된다.

 

소스코드

def partition(data, start, end):
    pivot = data[start] # 첫번째 값을 피봇으로 사용
    big_index = start + 1
    small_index = end
    
    while big_index <= small_index:
    	while(big_index <= small_index and data[big_index] <= pivot): big_index += 1
        while(big_index <= small_index and data[small_index] >= pivot) : small_index += 1
        
        if big_index <= small_index:
        	data[big_index], data[small_index] = data[small_index], data[big_index]
	
    # while문이 끝나면 small_index와 big_index가 엇갈린다.-> small_index < big_index
    data[start], data[small_index] = data[small_index], data[start]
    return small_index     

 

2. 로무토 partition

def partition(data, start, end):
    x = data[end]
    i = start - 1
    for j in range(start, end):
    	if data[j] <= x:
            i += 1
            data[i], data[j] = data[j], data[i]
    data[i+1], data[end] = data[end], data[i+1]
    return i+1

i : 피봇보다 작은 마지막 값

j : 피봇보다 큰 마지막 값

 

 

5. 이진 검색

• 키값과 비교하여 다음 검색 위치를 반으로 줄인다
• 데이터가 정렬되어 있어야 한다.

1. 중앙값 선택

2. 중앙값과 키값을 비교

3. 중앙값 > 키값 -> 좌측 검색

   중앙값 < 키값 -> 우측 검색

4. 찾을 때 까지 반복

소스코드

def binarySearch(data, key):
    start = 0
    end = len(data) - 1
    while start <= end:
    	mid = start + (end-start)//2
        if key == data[mid]:
        	return mid
        elif key < data[mid]:
        	end = mid - 1
        else: # data[mid] < key
        	start = mid + 1
    return -1            

재귀구조

def binarySearch(data, low, high, key):
    if low > high:
    	return -1
	mid = (low+high) // 2
    if key == data[key]:
    	return mid
    elif key < data[mid]:
    	return binarySearch(data, low, mid-1, key)
    else:
    	return binarySearch(data, mid+1, high, key)

 

6. 분할 정복 사례