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

 

피보나치 수열은 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

 

점화식은 $F_n = F_{n-1} + F_{n-2}$ 으로 정리된다.

(출처 https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98)

 

피보나치 수열은 여러 방법을 통해 구현할 수 있고

제일 쉽게 생각하는게 반복문과 재귀함수인거 같습니다.

재귀 함수를 이용한 풀이

#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(2^N)$ 입니다.

지수함수 그래프 개형을 보면 아시겠지만 n이 증가할수록 시간이 말도안되게 커집니다.

 

 

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

 

#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];
	}
}

1
1
2
3
5
8
13
21
34
55
89
144
(... 중략)
1548008755920

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

메모이제이션은 한마디로 계산하면서 이미 계산한값은 메모해둔곳에서 가져와서 계산하자 입니다.

수학 문제 풀때도 이미 계산한값 사용하는게 더 빠르니깐요.

 

소스코드를 간단하게 설명하자면

memo[100] 으로 이렇게 Array 를 만듭니다. 이게 메모장이구요

대충 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)$ 으로 크게 줄어듭니다.