[알고리즘] 분할 정복

분할 정복이란 말 그대로 

• 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
• 정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
• 통합(Combine): (필요하다면) 해결된 해답을 모은다.

 

거듭제곱을 통한 예제를 통하여 분할 정복을 알아보자.

기존의 함수를 구현한다면 O(n)의 시간 복잡도가 걸린다.

def Power(Base, Exponent):
	if Base == 0:
    	return 1
    result = 1 # Base^0는 1이므로
    for i in range(Exponent):
    	result *= Base
    return result

 

분할 정복 기반 알고리즘을 통한다면 O(log 2 n)의 시간 복잡도가 걸리는데 어떻게 이렇게 될 수 있을까?

어떤 정수 C^8 = C x C x C x C x C x C x C x C와 같이 구하는게 위의 방식에서 봤던 일반적인 사고다.

C의 8승을 나눠본다면 C^4 x C^4 = (C^4)^2 = ((C^2)^2)^2와 같이 표현할 수 있다.

이를 일반화한다면 아래와 같은 식이 나온다.

def Power(Base, Exponent):
	if Exponent == 0 or Base == 0:
    	return 1
    
    if Exponent % 2 == 0:
    	NewBase = Power(Base, Exponent/2)
        return NewBase * NewBase
    
    else:
    	NewBase = Power(Base, (Exponent-1)/2)
        return (NewBase * NewBase) * Base

 

 

# 분할 정복을 활용한 알고리즘

 

1. 병합 정렬

2. 퀵정렬

 

-> 병합 및 퀵 정렬은 아래 게시글 참고

2022.09.09 - [ALGORITHM/알고리즘 알아보기] - [알고리즘] 정렬2 - 합병, 퀵 정렬

[알고리즘] 정렬2 - 합병, 퀵 정렬

 

3. 이진 탐색(Binary Search, 이분 탐색)

 

• 정렬된 리스트에서 특정값을 찾아내는 방법으로, 가운데에 있는 항목의 키 값과 비교하여 해당 값보다 작은 경우 왼쪽에서 이진 검색을, 큰 경우에는 오른쪽에서 이진 검색을, 같은 경우 해당 값을 반환하게 된다.
• 정렬된 경우에만 사용 가능하다.

# 1) 반복 구조

def binarySearch(a, key):
    s, e = 0, len(a)-1
    
    while s <= e:
    	mid = s + (e-s) // 2
        if key == a[mid]:
            return mid
        elif key < a[mid]:
            e = mid - 1
        else:
            s = mid + 1
    return -1
    
    
    
 # 2) 재귀 구조
 
 def binarySearch(a, low, high, key):
	if low > high:
    	return -1
    else:
    	mid = (low+high) // 2
        if key == a[mid]:
        	return mide
        elif key < a[mid]:
        	return binarySearch(a, low, mid-1, key)
        else:
        	return binarySearch(a, mid+1, high, key)