[알고리즘]동적 계획법
1.동적계획법(Dynamic Programming, DP) 전체 문제를 작은 부분 문제로 나누어 해결하는 방법 동적계획법의 대표적인 예인 피보나치 수열을 통해 개념을 살짝 이해해보자. 피보나치 수열은 다음과 같다. 1,1,2,3,5,8,13,21,... 다음과 같이 N번째 값은 N-1번째 값과 N-2번째 값이 더해져서 만들어진다는 규칙이 있다. 그럼 이것을 점화식으로 표현해보면 F(N)=F(N-1)+F(N-2)와 같다. def fibo(n): if n==1: return 1 elif n==2: return 1 else: return fibo(n-2)+fibo(n-1) 위 코드대로 실행해보면 성공적으로 피보나치 수열이 구해지는 것을 볼 수 있다. 근데 문제점이 있다. 매개변수의 값이 너무 커지면 실행시간이..