알고리즘1

• [파이썬] '다이나믹 프로그래밍' 개념 및 예제 다이나믹 프로그래밍 => 한번 계산한 문제는 다시 계산 X !! (중복 줄이기) 언제 사용? 1. 큰 문제를 작은 문제로 나눌 수 있을 때 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일 다이나믹 프로그래밍과 분할 정복과의 차이점: 분할은 하지만, 서로 영향을 끼친다 (중복이 있음) ex) 피보나치 수열을 재귀적으로 처리하면 n이 커질수록 수행 시간 너무 커짐. # (재귀) 피보나치 def fibo(X): if x==1 or x==2: return 1 return fibo(x-1)+fibo(x-2) -> 탑다운 (큰 문제 해결을 위해 작은 문제 부름) 한번 구한 결과는 저장해두었다가 그대로 불러오자 ( 메모이제이션 기법 => 캐싱 ) #(재귀-메모이제이션) 피보나치 d= [0]*100.. Algorithm/이론 2021. 1. 6.