[Fibonacci에서의 세 가지(Recursion, Dynamic Programming,Bottom-Up Approach]

Fibonacci를 구하는 방법은 총 3가지가 있다.

 

 

Recursion

int Fibo(int num)
{

   if(num == 1)
      return 1;
   else if( num ==2 )
      return 1;
   else
      return Fibo(num-1)+Fibo(num-2);

}

그림1

재귀방식으로 짜는 방식은 이와 같이 반복이 일어난다. fibo(3)이 좌우로 두번 반복하는 낭비가 발생한다.

해당 방식은 시간복잡도가 O(2^n)으로 나타난다.

 

 

 

Dynamic Programming(Memoization)

이와 같은 반복되는 낭비를 막기 위해 Memoization 방식을 사용한다. 즉 위에 fibo(3),fibo(2) fibo(1) fibo(0)의 값을 저장해 놓은 뒤에 재 사용하는 것이다.

 

 

int Fibo(int num) {
	if(memo[num]) {
		return memo[num];
	} else {
		if(num<2) return n;
		memo[num]=Fibo(num-1)+Fibo(num-2);
		return memo[num];
	}
}

 

 

 

이와 같은 방식을 사용하면 시간 복잡도가 O(n)으로 줄어든다. 공간 복잡도 또한  O(n)이다.

 

 

 

Bottom-Up Approach

 

재귀를 사용하지 않고 반복문으로 해결하는 방법 또한 존재한다. 상대적으로 메모리를 아낀다.

 

int Fibo(int num) {

	int memo[3];
	memo[0]=0;
	memo[1]=1;
    
	for (int i=2; i<=num;i++) {
		memo[i]=memo[i-1]+memo[i-2];
	}
    
	return memo[num];
}

 

 

//메모리를 더 아끼는 법

int Fibo(int num) {

	int memo[3];
	memo[0]=0;
	memo[1]=1;
    
	for (int i=2; i<=num;i++) {
		memo[i%3]=memo[(i-1)%3]+memo[(i-2)%3];
	}
    
	return memo[num];
}

 

 

 

출처

그림1