[python] 동적 계획법과 분할정복 - 피보나치, 이진 탐색, 빠른 정렬, 병합 정렬 (업뎃중)

*본문은 <컴퓨팅 사고력 향상을 위한 문제해결과 알고리즘>(성균관대학교 출판부, 2017)와 사이트(https://wayhome25.github.io/cs/2017/04/15/cs-16/), 패스트캠퍼스 알고리즘 강의를 참고하여 작성되었습니다.

 

1. 정의와 예시

•동적 계획법: 가장 작은 문제부터 상향식으로 해결해 나가는데, 이 작은 문제가 중간~상위 문제와 중복되는 내용이며 이 작은 것을 위로 올라갈 때까지 계속 합쳐 나간다.

•분할 정복: 주어진 문제를 더 이상 분할할 수 없는 단위까지 계속 분할하여 부분 문제를 해결할 수 있는 해를 찾는 것. 동적 계획법과 차이점은, 가장 하위의 문제가 중간 및 상위 문제와 내용이 중복되지 않고 하향식 접근법(상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식)이다. 일반적으로 재귀함수로 구현한다(재귀함수는 이처럼 고급 알고리즘에서 많이 사용된다)
일반적인 재귀호출(대표적으로 팩토리얼)과는 다르다. 합병 정렬이 오히려 이 경우에 해당.

 

피보나치 수열 문제의 분할 정복  vs 동적계획법 풀이를 비교해보자.

 

•분할 정복(재귀) 풀이

def fibo(n):
	if n<=1:
        	return n
    return fibo(n-1) + fibo(n-2)

•동적 계획법 풀이

def fibo_dp(n):
	cache = [0 for i in range(n+1)] # n+1개
    # cache[0] = 0
    cache[1] = 1
    
    for i in range(2,n+1):
    	cache[i] = cache[i-1] + cache[i-2]
        
    return cache[n]

이런 식으로 배열 활용 가능.

 

 

2. 분할 정복의 대표적 (정렬) 예

1) 이진 탐색(binary search)

def binary_search(array, target):
    array.sort()
    front = 0
    back = len(array)-1
    while front<=back:
        mid = (front+back)//2
        if array[mid] == target:
            return mid
        elif array[mid]>target:
            back = mid-1
        else:
            front = mid+1
    return None


# 테스트 코드
if __name__ == "__main__":
    aList = [i*2 for i in range(11)]
    target = 9
    result = binary_search(aList,9)

    if result:
        print(aList[result])
    else:
        print("찾으시는 타겟 {}가 없습니다.".format(target))

재귀적으로 구현하면 아래와 같다.

ef binary_search_recursion(target,front,back,array):
    if front > back:
        return None
    
    mid = (front+back) // 2

    if array[mid] == target:
        return mid
    elif array[mid]>target:
        back = mid-1
    else:
        front = mid+1

    return binary_search_recursion(target,front,back,array)


#테스트 코드
if __name__ == '__main__':
    alist = [i*3 for i in range(6)]
    target = 6
    index = binary_search_recursion(target,0,10,alist)
    print(index)

 

2) 빠른 정렬(quick sort)

이게 피봇 이용해서 하는 그 녀석. 다만 타겟값을 찾을 때의 풀이와 헷갈리면 안된다. 피봇을 중간에 있는 값으로 잡는게 아니란 뜻이다. 맨 처음걸 피봇으로 잡고, 배열[1:마지막]을 다루는 것. 새로운 배열 2개를 생성하고, 피봇보다 작은 원소는 한 배열, 큰 원소는 다른 한 배열로 넣는 작업을 계속한다. 아~ 이렇게 하니 내가 공부했던 그 그림이 생각난다.

def quicksort(arr):
    if len(arr)>1:
        pivot = arr[0]
        lesser = [element for element in arr[1:] if element>pivot]
        greater =  [element for element in arr[1:] if element<=pivot]
        return quicksort(lesser) + [pivot] + quicksort(greater)
    else:
        return arr



arr = [3, 5, 1, 2, 9, 6, 4, 7, 5]
print(quicksort(arr))

나는 try/except 로 했는데 왜 내 코드는 안되지...? 이거 고민하는 지점부터 다시 시작할 것.

 

3) 병합 정렬(merge sort)