피보나치 수열

피보나치 수열을 어떻게 표현할 수 있을까?

F(n) = F(n-1) + F(n-2) 니까

대부분, 재귀함수로 구현한다.

int F(int n)

{

if(n == 1 || n == 2)

return 1;

else

return F(n-1) + F(n-2);

}

근데, 이러면 중복된 연산이 많아진다.

Time Complexity = O(2^(n/2)) 이라고 한다.

DP를 쓰면 문제가 쉽게 해결된다.

이전의 계산되는 F(n)값을 return하는게 아니라 배열에 저장하고

다음 계산때는 배열에 저장한 값을 활용한다.

이렇게 문제를 해결하면 아래와 같다.

memset(DP, -1, sizeof(DP));

DP[1] = DP[2] = 1;

int F(int n)

{

if(DP[n] == -1)

DP = F(n-1) + F(n-2);

else

return DP[n];

}

와우! 매우 간단하게 해결됬다.

Time Complexity = O(n) 으로 해결된다.

끝~!

두 문제 해결의 차이는 재귀적이냐, DP냐 일 뿐.

* 보충 설명

꼭, DP가 아니여도 선형적으로 접근할 수 있다.

재귀가 아닌 for문을 사용하면 된다.

이 방법은 피보나치 수열은 이전의 값을 계속하여 재활용하기 때문에

int p1, p2, p3;

p1 = p2 = 1;

for(int i=2;i<n;i++)

{

p3 = p1 + p2;

p1 = p2;

p2 = p3;

}

// p3가 답

로 구현할 수 있다.

Time Complexity = O(n) 이다.

위 DP랑 선형 접근의 차이는 계속하여 피보나치 값을 계산할 때이다.

DP를 사용하면 이전의 F(11223)의 값을 계산했을 때 값을 저장하고 그 이하의 <= n 이하의 피보나치 수열 값을 자동적으로 계산하기 때문이다.

그냥, F(11223)을 계산하면 '다음 계산에서 11223 보다 작은 피보나치 값을 계산할 필요가 없다'라고 이해하면 된다.