피보나치 함수 (Dynamic programming - 동적계획법) ★☆☆

n번째 피보나치 수열을 구하기 위해 사용되는 리스트는 dp이다. (dynamic programming에서 메모제이션 역할)

def fibo(n)을 분석해보면,

 

동적계획법에서 계속 사용되는 수를 dp 리스트에 저장하여 dfs로 피보나치를 구할 때 중복되는 값을 빠르게 사용한다.

 

1. n == 0일 경우, 0을 리턴한다.

2. n == 1일 경우, 1을 리턴한다.

 

위 두 경우는 점화식 An = An-1 + An-2에서 초기값에 해당하기에 리턴값을 지정해놓는다.

 

3. dp[n] != -1일 경우,

dp 리스트는 초기에 -1로 설정되어 있다. 따라서 피보나치 수열의 n번째 값이 구해지지 않았다면 dp[n] = -1 이다.

따라서 dp[n] != -1는 이미 n번째 값이 구해져 있는 경우이다. 그러므로 그대로 저장된 값을 사용하여 dp[n]을 리턴한다.

 

4. 위 모든 경우에 해당하지 않는 경우 (dp[n] == -1일 경우)

dp[n] = fibo(n-1) + fibo(n-2) 식으로 dp[n]을 구한다.

fibo(n-1)은 결국 dp[n-1]을, fibo(n-2)는 dp[n-2]를 리턴할 것이므로 점화식 An = An-1 + An-2 을 만족한다.

 

위 원리에서 중요한 것은 Dynamic 에서 저장하는 값 dp를 어떻게 잘 활용하느냐 라고 생각한다.

 

위 def fibo(n)를 간단히 정리하면,

 

" An가 dp에 저장 X 경우 -> An-1 An-2 로 내려감 -> 각각 저장 X 경우 또 내려감 -> ...... -> n=1, n=0 일 경우 값 존재

-> 다시 올라가면서 dp에 하나씩 저장 및 이용 "

 

위 문제에서는 0과 1이 몇 번 쓰이는지 알아내야 하므로 dp2[i][j] 라는 2차원 리스트 (2 * 41) 를 사용하여 i는 0 과 1로 j 번째 숫자에 각각 사용된 개수를 표시한다.

 

따라서 n == 0, n == 1 경우 초기값으로 위 코드와 같이 넣어주고,

dp[n] = fibo(n-1) + fibo(n-2) 밑에

dp2[0][n] = dp2[0][n-1] + dp2[0][n-2] 

dp2[1][n] = dp2[1][n-1] + dp2[1][n-2]

으로 n-1번째와 n-2번째 쓰인 0과1의 개수를 더해서 저장해준다.

 

 

동적계획법을 너무 오랜만에 접하는 것이라 코드를 짤 때 혼란스러웠다.

자주 사용되는 만큼 많은 문제풀이를 통해 익숙해져야겠다.