피보나치 수열 메모이제이션 연습하기

 

안녕하세요 진공이입니다.

요즘 알고리즘을 조금씩 공부하고 있는데 문제를 풀다 보니 기존 상식으로는 도저히 안풀리는 문제들이 있더라고요.

그래서 검색을 해 보니 여러가지 기법이 있다고 합니다.

그 중에서 메모이제이션 기법을 사용해 피보나치 수열의 n번째 수를 구하는 프로그램을 연습 해 보았습니다.

 

문제 링크: https://codeup.kr/problem.php?id=1916&rid=0

(재귀함수) 피보나치 수열 (Large)

---

 

피보나치 수열이란?

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

 

1, 1, 2, 3, 5, 8, 13 ... 순으로 진행됩니다.

1+1 = 2

1+2 = 3

2+3 = 5

3+5 = 8

5+8 = 13

.

.

.

이렇게 끝없이 진행되는 수열입니다.

---

 

아래는 제가 작성한 코드입니다.

#include <stdio.h>

long long int arr[1000001] = {1, 1};

int fibo(int n){
	if(n < 2) return n;
	if(arr[n] != 0){
		return arr[n];
	}
	else
	{
		arr[n] = (fibo(n-1)+fibo(n-2))%10009;
		return arr[n];
	}
}

int main(void){
	int a;
	scanf("%d", &a);
	printf("%d", fibo(a));
}

피보나치 수열의 n번째 수를 10009로 나눈 나머지를 출력하는 프로그램입니다.

처음에는 이해하는 데 많은 애를 먹었지만 이해하고 나니

생각보다 어렵지 않았습니다.

 

한 번 나온 값은 배열에 저장 해 놓았다가 똑같은 값이 있으면 다시 계산하지 않고 배열에 있는 수를

가져다 쓰는 맥락입니다.