동적계획법
-
[알고리즘] 동적 계획법 & 분할 정복Algorithms & Data Structure 2021. 7. 12. 18:33
본 내용은 패스트캠퍼스 올인원 알고리즘 강좌 내용을 요약/정리한 노트입니다. 동적 계획법 상향식 접근법. 큰 문제를 작은 문제로 나눠서 해결한다. Memorization 기법을 사용하여 이전에 계산한 값을 다시 계산할 필요 없게하여 속도 향상시킨다. 분할 정복 하양식 접근법. 즉, 큰 문제를 위해 아래로 내려가서 작은 문제 답을 구한다. 재귀함수 (recursive call)로 구현한다. 예시. 피보나치 수열 피보나치 수열이란 즉, 피보나치(0)과 피보나치(1)의 값이 주어지고 그 이후부터는 앞의 값 + 앞앞 값의 합으로 결정된다. 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Recursive Call로 피보나치 수열 구현 def fibo(num): if num