알고리즘 - 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
– 위키백과

동적 계획법 vs 재귀 알고리즘

문제를 반복해서 해결해 나가는 모습이 재귀 알고리즘과 닮아있다.

그러나

• 동적 계획법은 그 결과를 기록(Memoization)하고 이용한다는 점
• 여러 개의 하위 문제(Overlapping Subproblem)를 기록한 결과를 이용하여 해결한다는 점

이를 통해 동적 계획법은 성능적 향상뿐만 아니라 부분 문제를 해결함으로써 전체 문제를 해결할 수 있게 된다!

자료1) 동적 계획법 예시 (피보나치 수열)

1. 재귀함수

input = 20

def fibo_recursion(n):
    if n == 1 or n == 2:
        return 1
    return fibo_recursion(n - 1) + fibo_recursion(n - 2)

print(fibo_recursion(input))

2. 동적 계획법

input = 50

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장한다
memo = {
    1: 1,
    2: 1
}


def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:
        return fibo_memo[n]

    nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
    fibo_memo[n] = nth_fibo
    return nth_fibo


print(fibo_dynamic_programming(input, memo))

이를 비교하여 코드를 실행하면, 동적 계획법을 이용 하였을때 연산이 훨씬 빠름을 확인 할 수 있다.

그 이유는

1. 재귀 알고리즘의 경우 실행했던 작업을 계속 다시 한다. 즉, 이미 시켰던 똑같은 작업을 다른 곳에서 다시 새롭게 하고 있는 것.

2. 동적 계획법의 경우 메모를 통해 만약 메모에 그 값이 있다면 바로 반환하고, 없다면 피보나치 값을 메모에 기록하여 원할때 찾아서 사용하면 되기 때문.