목록2025/01/08 (1)
CS log
Dynamic Programming
DP란메모리 공간을 약간 더 사용하면 연산 속도를 더 비약적으로 증가시킬 수 있는 방법top down과 bottom up 방식이 있다. + 메모이제이션 기법 대표적인 문제로는 피보나치 수열이전 두 항의 합을 현재의 항으로 설정하는 수열점화식(인접 3항간 점화식)을 이용하여 표현하면, a_n+2 = f(a_n+1 , a_n) = a_n+1 + a_n최종적인 피보나치 수열은 프로그래밍에서는 이를 배열이나 리스트로 표현가능. 수열 자체가 여러 개의 수가 규칙에 따라 배열된 형태를 의미하기 때문이다.f(n)을 표현할 때 f(2),f(1)은 항상 1이므로 호출을 정지한다. 이를 코드로 표현하면 아래와 같다.def fibo(n) : if n==1 or n==2 : return 1 else : fi..
CS/Algorithm
2025. 1. 8. 01:44