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

DP

• 동적 계획 (Dynamic Programming) 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.
• 동적 계획 알고리즘은 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다. 

 

피보나치 수 DP 적용

• 피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있다.

 

1) 문제를 부분 문제로 분할한다.

• Fibonacci(n) 함수는 Fibonacci(n-1)과 Fibonacci(n-2)의 합
• Fibonacci(n-1)은 Fibonacci(n-2)와 Fibonacci(n-3)의 합
• Fibonacci(2)는 Fibonacci(1)과 Fibonacci(0)의 합
• Fibonacci(n)은 Fibonacci(n-1), Fibonacci(n-2), .... Fibonacci(2), Fibonacci(1), Fibonacci(0) 의 부분집합으로
  나뉜다. 

2) 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구한다.

 

3) 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.

 

피보나치 수 DP 적용 알고리즘

def fibo2(n):
    f = [0] * (n + 1)
    f[0] = 0
    f[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] + f[i-2]
        
    return f[n]

 

DP의 구현 방식

• recursive 방식 : fib1()
• iterative 방식 : fi2()

 

• memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능면에서 보다 효율적이다.
• 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문이다.

 

---