재귀
-
동적 프로그래밍 (Dynamic Programming)Software/Algorithm : 알고리즘 2018. 9. 17. 23:50
사용 조건 작은 문제의 최적 솔루션이 그 보다 더 큰 문제의 최적 솔루션에 포함되는 경우 재귀적인 방법으로 구현 시 중복 호출로 인한 큰 비용/비효율이 발생하는 경우 피보나치 수열 피보나치 수열은 동적 프로그래밍의 사용 동기와 조건, 구현을 가장 쉽고 명료하게 확인할 수 있는 예제. fn = fn-1 + fn-2 (n >= 3) f1 = f2 = 1 (n = 1, 2) 재귀호출 방식 의사 코드 (Pseudo-code) Fibonacci(n) { if (n = 1 or n = 2) then return 1; else return Fibonacci(n - 1) + Fibonacci(n - 2); } 구현 (Implement) // Not to use dynamic programming.. int fibona..