Dynamic Programming(DP) 알고리즘 - 동적프로그래밍, Python으로 푸는 피보나치

Dynamic Programming 

큰 문제를 나누어 작은 문제로 푸는 것 

하나의 문제는 단 한 번의 풀이만 한다. 

 

 

Dynamic Programming 과 Recursion(재귀)의 차이점 

DP와 재귀는 얼핏보면 '같은 문제가 반복적으로 일어나는 점' 에서 비슷하다고 생각할 수 있다.

하지만, 큰 차이점은 일반적인 재귀를 단순히 사용하면  동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다.

가장 대표적인 예시는 피보나치 함수이다. 



DP 조건

두 가지 조건을 만족해야 한다.

1. 같은 문제가 반복적으로 발생

2. 최적 부분 구조 

동일한 작은 문제들이 반복적으로 일어날 때, 같은 문제는 항상 정답도 같다. 즉, 중복 사용이 가능하다. 

 

 

DP 문제 풀이 방법

모든 작은 문제는 한 번만 풀어야 한다.

이후 큰 문제를 풀 때 똑같은 작은 문제가 일어나면 앞서 풀었던 것을 이용하여 푼다.

dp[0], dp[1], dp[2], dp[3] 이렇게 작은 문제를 해결하다 보면 규칙을 발견하게 된다. 

때문에 dp[4]를 해결할 때 즈음에는 이전에 구해놓은 작은 문제들인 dp[0],dp[1],dp[2],dp[3]을 이용해 점화식을 도출할 수 있다.

[1] DP로 풀 수 있는 문제인지 확인
[2] 문제의 변수 파악
[3] 변수 간 관계식 만들기 (점화식)
[4] 메모하기 memoization
[5] 기저 상태 파악하기
[6] 구현하기 

 

DP 구현 방법 

DP는 2가지 방법으로 구현할 수 있다. 

 

1. Bottom-Up : 반복문 사용

아래에서부터 계산을 수행하고 누적시켜 전체적인 큰 문제를 해결하는 방법이다.

위에서 잠깐 설명했던 것처럼 dp[0]부터 dp[n-1]까지의 값을 반복문을 사용해서 점화식으로 결과를 낸다. 

 

 

2. Top-Down : 재귀 사용 

위에서부터 호출을 시작해 dp[0]까지 내려가 결과 값을 찾는 방법이다. 피보나치 문제가 가장 대표적이다.

f(n) = f(n-1) + f(n-2) 의 식과 같이 동일한 계산이 반복적으로 나오면서 위에서부터 호출을 한다. 

 

 

 

 

DP의 장점

동적계획법을 적절하게 사용하면 매우 빠르게 해를 얻을 수 있다. 

지수 복잡도 알고리즘을 다항 시간으로 줄여주기도 하고, 같은 다항 시간 알고리즘도 차수를 낮출 수 있다.

 

DP 예시 

피보나치 수열은 다음과 같은 재귀의 형태를 가진다. 
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) when n > 1

Dynamic Programming을 이용하여, 피보나치 수열을 나타내어라 

 

Python으로 풀기 

memo = [0 for i in range(100)]  #메모이제이션 공간. 전역 변수이므로 0으로 초기화
memo[0] = 0
memo[1] = 1

def fibonacci(n) :
  if memo[n]!=0 :#메모가 있는지 확인(0으로 초기화되었으므로 0이 아니라면 메모가 쓰인 것임)
    return memo[n]  #메모 리턴
  memo[n]=fibonacci(n-1) + fibonacci(n-2) #작은 문제로 분할
  return memo[n]