dynamic programming1 DP란 무엇인가? 동적 계획법 동적 계획법(dynamic programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 1. 동적 계획법의 조건 1) 부분 반복 문제(Overlapping Subproblem) 동적 계획법의 등장은 피보나치 수열에서 시작되었다고 한다. 피보나치 수열을 재귀 함수로 표현할 시, 이와 같다. fib(1) = 1; fib(2) = 1; fib(n) = fib(n-1) + fib(n-2); // 메소드로 표현한 피보나치 수열 int fib(int n) { if (n 2021. 8. 4. 이전 1 다음
