피보나치 #동적프로그래밍 #dp #다이나믹프로그래밍 #최적부분구조 #재귀비효율1 [알고리즘] 동적 프로그래밍, 다이나믹 프로그래밍, DP :: seoftware 정의 동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함(최적부분구조)되어 있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 뜻한다. 정의로 유추할 수 있는 것 -> 최적부분구조가 발견되고, 재귀를 사용했을 때 중복 호출이 많을 때는 DP를 사용한다! 예시 - 피보나치 int fibo(int n) { if(n == 0) return 0; else if(n == 1) return 1; else return fibo(n-1) + fibo(n-2); } 코드는 간단해보이지만 중복 호출이 많기 때문에 비효율적이다. fibo(7)을 호출하면 fibo(2)가 몇번이나 호출되는지 확인해보자 fibo(7)을 구하기 위해 f.. 2020. 2. 20. 이전 1 다음
