동적계획법(Dynamic Programming) - 피보나치 숫자

f[n] = f[n-1] + f[n-2]

위의 식을 계산하는 가장 빠른 방법은?

1. Fibonacci Numbers
: f[n] 부터 시작해서 f[1]을 끝으로 2의 n승 회의 연산이 필요, 너무 많은 연산이 반복됨. 단순분할정복이라고도함.

int finbonacci (int n) {
  int[] f = new  int[100];  
  /*
  if(n==1 || n==2) {
  return 1;
  } else {
  return finbonacci(n-2) + finbonacci(n-1);
  }
  */
  if(n == 1) return 1;
  if(n == 2) return 1;
  return f[n] = finbonacci(n - 1) + finbonacci(n - 2);
}

 

2. Memoization
: 이미 계산된 f값(중간 계산결과)을 캐싱함으로써 중복계산을 피하는 방법. n회의 연산만 필요하게 됨.

int memoization(int n) {
  int[] f = new  int[100];  
  /*
  if(n==1 || n==2) {
  	return 1;
  } else if(f[n] > -1) {		// f[n]을 -1로 초기화 했다는 가정, 즉 f[n] > -1은 이미 계산된 값
  	return f[n] ;				// 이미 계산된 값을 재사용
  } else {						// 새로 계산한 값을 캐시에 저장
    f[n] = finbonacci(n-2) + finbonacci(n-1);
    return f[n];
  }
  */
  if(n == 1) return 1;
  if(n == 2) return 1;
  if(f[n] != 0) return f[n];
  return f[n] = memoization(n - 1) + memoization(n - 2);
}

 

3. Buttom-Up

구하려는 f[n]에서 시작하는 recursion이 아니라, 1부터 시작해서 순서대로 계산한다. 따라서 f[n]을 계산하려는 시점에 이미  f[n-1]과 f[n-2]가 계산되어 있으므로 중복계산이 없음. 순환식에서 일반적, 상식적으로 사용.

f[1] = 1;  f[2] = 1;
for(int i = 3; i <=n; i++) {
  f[i]=f[i-1]+f[i-2];
  return f[i];
}

 

4. 1, 2성능비교 

public static void main(String[] args) {
  FibonacciNumbers fn = new FibonacciNumbers();
  long startF = System.currentTimeMillis();
  System.out.println(fn.finbonacci(30));
  long endF = System.currentTimeMillis();
  long startM = System.currentTimeMillis();
  System.out.println(fn.memoization(30));
  long endM = System.currentTimeMillis();

  System.out.println("피보나치 실행시간 : " + (endF - startF));		// 206
  System.out.println("DP 실행시간 : " + (endM - startM ));		   // 128
}

30번째 수를 구할 시 단순분할 206 vs DP 128

 

참고한 자료. 아주 좋은 설명.
www.youtube.com/watch?v=K15qLnKKrow&t=499s

www.youtube.com/watch?v=FmXZG7D8nS4