피보나치수열
-
#Dynaminc_programming #코딩공부Data miner 2019. 9. 11. 17:59
Dynamic programming을 위해서는 두 가지의 조건이 필요하다. 최적 부분 구조와 중복되는 부분 문제가 그 조건에 해당한다. - 조건 1) 먼저, 최적 부분 구조(optimal substructure)의 경우에는 부분 문제들의 최적을 답을 이용해서 원래 문제의 최적의 답을 구하는 방식이다. 특정 시점의 최적값을 구하기 위해서 바로 전 시점의 최적값들의 비교를 통해서 현 시점의 최적값을 구하는 경우를 생각해보자. 이전 시점의 최적값이 고정값인 경우도 있고(피보나치 수열의 경우) 혹은 여러 경우의 수에 따라서 값이 달라져 최적 부분 구조를 찾기 위해서 여러 조합을 후보로 생각해야 할 수도 있다. - 조건 2) 재귀 호출시 중복(overlapping recursive calls)일 경우, 재귀적 해..