728x90 반응형 알고리즘/DP37 [DP 개념] Dynamic Programming#1_피보나치 수열,Memoization,Bottom-up 방식 피보나치 수열 f(n) = f(n-1) + f(n-2) (단, n>2) 이것을 자바 코드로 구현해 보면, fib(3)이면 결과는 2일 것이다. f(1)=1이고,f(2)=1이기 때문에 f(3)은 2가 된다. Memoization 피보나치 수열은 이미 계산한 수를 중복으로 계산하는 경우가 발생하기 때문에 굉장히 비효율적이다. 계산의 중복을 피하기 위해 이미 계산된 값을 기억해두는 것. Memoization에서 저장해 놓은 배열을 cache 라고 부른다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class DP { static int[] f = new int[10000]; static int fib(int n) { if (n == 1 || n == 2) { ret.. 2021. 7. 26. 이전 1 ··· 7 8 9 10 다음 728x90 반응형
