[알고리즘] Fibonacci Number

피보나치 숫자를 구하는 알고리즘을 Recursion, Memoization, Dynamic Programming으로 해볼 것이다.

By Recursion

int F(int n)
{
	if(n<2) return n;
	return F(n-1) + F(n-2);
}

n이 7인 경우의 그림 예시

• 모든 노드는 자기 이하의 노드 개수를 반환하고, 값을 생성하는 건 Leaf노드 뿐이다.
• 즉 중간 노드는 자식 노드의 값을 받아서 더하기만 할 뿐이다.
  

느린 이유는 겹치는 노드가 많고 중복 계산이 많다.
따라서 이를 해결하기 위한 아이디어는 이미 계산한 값을 중복 계산하지 않기 위해 메모해놓는 것이다.

By Memoization

int FF[1000]; // 메모지
int init()
{
	for(int i=2; i<1000; i++)
    {
    	FF[i] = -1; // 아직 값 모르겠는데?
    }
    FF[0] = FF[1] = 1;
}
int F(int n)
{
	if(FF[n] != -1) // 값 알아?
    {
    	return FF(n); 
    }
    
    FF[n] = F(n-1) + F(n-2); // 모르면 계산해 
    return FF[n];
}

위와 같이 한 번 계산한 값은 다시 계산하지 않도록 미리 저장만 해놓아도
n에 대한 FF배열의 값은 죽어도 한 번만 계산된다.

그러나 베이스가 재귀라서 느리고
무지성으로 돌리고 있어서 성능 속도를 알기가 어렵다고 한다.

By Dynamic Programming

int FF[1000];
int F(int n)
{
	FF[0] = FF[1] = 1;
    for(int i=2; i<1000; i++)
    {
	    FF[i] = FF[i-1] + FF[i-2];
    }
    
    return FF[n];
}

DP를 활용한 방법은 위와 같이 재귀를 사용하지 않고
단순히 앞쪽 배열의 값을 사용해서 이후 값을 채워나간다.

Memoization 과의 차이는 무엇일까?
Memoization은 단순히 중복 호출되는 것을 메모해둔 것이며,
테이블을 채우는 순서를 정할 수 있으면 DP로 하면 된다고 한다.

또한 DP는 처음부터 끝까지 FF[i] = FF[i-1] + FF[i-2]라는 점화식이
변하지 않고 유지되며, 이를 통해 답을 얻을 수 있다.