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

본 내용은 패스트캠퍼스 올인원 알고리즘 강좌 내용을 요약/정리한 노트입니다.

동적 계획법

• 상향식 접근법. 큰 문제를 작은 문제로 나눠서 해결한다.
• Memorization 기법을 사용하여 이전에 계산한 값을 다시 계산할 필요 없게하여 속도 향상시킨다.

분할 정복

• 하양식 접근법. 즉, 큰 문제를 위해 아래로 내려가서 작은 문제 답을 구한다.
• 재귀함수 (recursive call)로 구현한다.

예시. 피보나치 수열

피보나치 수열이란

즉, 피보나치(0)과 피보나치(1)의 값이 주어지고 그 이후부터는 앞의 값 + 앞앞 값의 합으로 결정된다.

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Recursive Call로 피보나치 수열 구현

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

 

동적 계획법 으로 피보나치 수열 구현

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]

 

구현 프로세스 확인

 

이 경우는 fibo_dp(3)을 실행한 결과 값이다. 오른쪽 노란색 결과값을 보면 알 수 있듯이, 처음에 0 과 1이 값으로 들어오고, 0+1=1의 값이 fibo_dp(2)로 들어온다. 그 뒤, fibo_dp(3) = fibo_dp(2) + fibo_dp(1) 로 결과 2를 갖는다. 

Go to GitHub