[C] 피보나치 수열과 메모이제이션

피보나치 수열은 수학에서 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

점화식은 Fn = Fn-1 + Fn-2으로 정리된다.

재귀 함수를 이용한 풀이

#include <stdio.h>
long long fibo(int n);
 
int main(){
	printf("%lld", fibo(10));
	return 0;
}
 
long long fibo(int n){
	if (n < 2) return n;
	return fibo(n-1) + fibo(n-2);
}

당장 fibo(100)만 넣어보면. 프로그램이 계산하다가 뻗어버리는 모습을 볼 수 있다.

불필요한 호출이 일어나서 프로그램이 느려지는건데 간단히 fibo(10) 을 계산하려면 fibo(9), fibo(8) 이 호출되고 fibo(9)가 다시 fibo(8), fibo(7) 을 호출하게 되는데 중복되는 계산이 많이 생기게 된다. 이때 시간복잡도는 O(2N)이다.

메모이제이션을 이용한 풀이

#include <stdio.h>
long long fibo(int n);
 
//배열들 초기값은 0이다 
long long memo[100] = {1,1}; 
 
int main(){
	for (int i = 1; i<=60; i++) printf("%lld \n", fibo(i));
	return 0;
}
 
long long fibo(int n){
	if (n < 2) return n;
	if(memo[n] != 0){ //메모되어있다면 
		return memo[n];
	} else { //메모안되어있다면 
		memo[n] = fibo(n-1) + fibo(n-2);
		return memo[n];
	}
}

메모이제이션을 활용하면 60항까지 출력을해도 무리가 없다.

메모이제이션은 한마디로 계산하면서 이미 계산한값은 메모해둔곳에서 가져와서 계산하자 이다. 수학 문제 풀때도 이미 계산한값 사용하는게 더 빠르기 때문이다.

 

소스코드를 간단하게 설명하자면 memo[100] 으로 이렇게 배열을 만든다. 이게 메모장이고 대충 100항까지 출력한다는 심산으로.. 그리고 자동으로 안에있는 값은 0으로 초기화 되고 1,2 번째 항까지 값은 1인걸 알고있다.

 

fibo(5) 이라는 값을 계산한다고 과정하고 프로그램의 동작 과정을 간단하게 보면

 

fibo(5) 호출 -> memo[5] 이 없으므로  memo[5] = fibo(4) + fibo(3)

fibo(4) 호출 -> memo[4] 가 없으므로 memo[4] = fibo(3) + fibo(2) 

fibo(3) 호출 -> memo[3] 가 없으므로 memo[3] = fibo(2) + fibo(1) <- 알고있음

fibo(2) 호출 -> memo[2] 가 없으므로 memo[2] = fibo(1) + fibo(0) <- 알고있음

fibo(2) 호출  -> memo[2] 가 있네? 바로 return memo[2]!

 fibo(3) 호출 -> memo[3] 이 있네? 바로 return memo[3]!

이런식으로 메모해온걸 뽑아오는거다.

이때 시간복잡도는 O(N) 으로 크게 줄어든다.

 

[C] 피보나치 수열과 메모이제이션 - 파일의 IT 블로그 (tistory.com)