동적계획법과 분할정복 : Dynamic Programing & Divide and Conquer

- 동적 계획법(Dynamic Programing)

-> 입력 크기가 작은 부분의 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분문제를 해결하여 최종적으로 전체 문제를 해결하는 알고리즘.

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

-> Memorization 기법을 사용 : 프로그램 실행 시 이전 단계에서의 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행속도를 빠르게하는 기술.

-> 문제를 잘게 쪼갤 때, 부분문제는 중복되어 재활용됨. ex)피보나치 수열

- 분할정복(Divide and Conquer)

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

-> 하향식 접근법으로, 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식. ex) 재귀함수

-> 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음. ex)병합 정렬, 퀵 정렬

 

-공통점과 차이점

-> 공통점 : 문제를 잘게 쪼개서, 가장 작은 단위로 분할한다.

-> 차이점 :

      1) 동적계획법 : 부분문제는 중복되어, 상위 문제 해결 시 재활용됨. (Memorization 기법 사용)

      2) 분할정복 : 부분문제는 서로 중복되지 않음. (Memorization 기법을 사용하지 않음)

 

- 동적계획법과 알고리즘 이해

-> 피보나치 수열 : n을 입력 받아서 다음과 같이 계산됨. n을 입력받았을 때 피보나치 수열로 결과 값을 출력하시오.

fibo(0) = 0

fibo(1) = 1

fibo(2) = 1

fibo(3) = 2

fibo(4) = 3

fibo(5) = 5

fibo(6) = 8

 

#구현

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

#동적계획법활용(DP)

def fibo_dp(n):
    cache = [0 for _ in range(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]
 
print(fibo_dp(6))

 

동적계획법 문제풀이 순서

1. 부분문제를 정의한다.

2. 점화식을 구한다.

3. 문제를 해결한다.

- 아이디어