[알고리즘3] 동적계획법과 분할정복

 

---

동적계획법(DP: Dynamic Programming) 

동적계획법이란,

입력크기가 작은 부분의 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 큰 크기의 문제를 해결하는 방법.

최종적으로 전체 문제를 해결하는 알고리즘이다.

상향식 접근법으로, 가장 최하위 해답을 구한 후 해당 결과값을 이용해서 상위 문제를 풀어가는 방식.

 

memorization 기법

프로그램 실행시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행속도를 빠르게 하는 기술.

문제를 잘게 쪼갤 때 부분문제는 중복되어 재활용 된다.

예) 피보나치 수열 문제

---

분할정복(Divide and Conquer)

분할정복이란

문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘.

하향식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식이다.

일반적으로 재귀함수를 많이 사용한다.

문제를 잘게 쪼갤 때, 부분문제는 서로 중복되지 않는다.

예) 병합정렬, 퀵정렬 등 (고급정렬의 기법)

 

 

 

동적계획법과 분할정복의 공통점과 차이점

 

공통점:

문제를 잘게 쪼개서 가장 작은 단위로 분할한다.

 

차이점:

동적계획법: memorization O, 부분문제 중복 O

분할정복: memorization X, 부분문제 중복 X

 

 

 

 

---

파이썬으로 동적계획법, 분할정복 구현하기

 

재귀함수 활용

def fibo(num):
    if num <= 1:
        return num
    return fibo(num - 1) + fibo(num - 2)
    
fibo(1) = 1
fibo(2) = 1
fibo(3) = 2 # fibo(2) + fibo(1)
fibo(4) = 3 # fibo(3) + fibo(2)

 

동적계획법 활용

1. 작은 문제를 풀어야 상위 문제를 풀 수 있다. f(3)을 풀어야 f(4)를 풀 수 있다.

2. memorization

f(4)는 f(0) 두번, f(1) 세번, f(2) 2번, f(3) 1번 중복된다. 이 값을 미리 cache 배열에 저장해놓고 가져다 사용한다.

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