동적 계획법(Dynamic Programming)과 분할 정복(Divide and Conquer)

동적 계획법(DP, Dynamic Programming)

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용하여 보다 큰 크기의 부분 문제를 해결
• 위 단계를 반복하며 전체 문제를 해결하는 알고리즘
• 상향식 접근법으로, 가장 최하위 해답을 구한 후 이를 저장해 다음 결과값을 풀어나가는 방식
• Menoization(메모이제이션)
  • 프로그램 실행시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 해 실행 속도를 빠르게 하는 기술
• 예) 피보나치 수열

def fibo_dp(num):
    cache = [0 for ind in range(num+1)] 
    cache[0] = 0 
    cache[1] = 1 
    for ind in range(2, num+1): 
    	cache[ind] = cache[ind-1] + cache[ind-2] 
    
    return cache[num]

분할 정복(Divide and Conquer)

• 문제를 나눌 수 없을 때까지 나누어 각각을 풀면서 다시 합병하여 문제의 답을 얻는 방법
• 하향식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 해답을 구하는 방식 --> 재귀함수로 구현
• 문제를 잘게 쪼갤때, 부분 문제는 서로 중복되지 않음
• 예) 퀵정렬, 병합정렬

def quick_sort(arr): 
    if len(arr) <= 1: 
    	return arr 
    pivot = arr[len(arr) // 2] 
    lesser_arr, equal_arr, greater_arr = [], [], [] 
    for num in arr: 
    	if num < pivot: 
        	lesser_arr.append(num) 
        elif num > pivot: 
        	greater_arr.append(num) 
        else: equal_arr.append(num) 
    
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    
    return merged_arr

 

참조 : https://www.fun-coding.org/Chapter14-dp_divide.html