[CodeUp] 1916번 "피보나치 수열 (Large)" C언어 풀이

문제

피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다. 첫 번째 수와 두 번째 수는 모두 11이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 피보나치수열을 나열해 보면 다음과 같다.

자연수 NN을 입력받아 NN번째 피보나치 수를 출력하는 프로그램을 작성하시오.

단, NN이 커질 수 있으므로 출력값에 10,00910,009를 나눈 나머지를 출력한다.

입력 예시

7

출력 예시

13

 

답안

코드

#include <stdio.h>

int arr[201];

int f(int a){
    if(a < 3)
        return 1;
    if(arr[a] != 0)
        return arr[a];
    return arr[a] = (f(a - 1) + f(a - 2)) % 10009;
}

int main(){
    int a;
    scanf("%d", &a);
    printf("%d", f(a));

    return 0;
}

 

풀이

처음 피보나치수열을 풀기 위하여 문제에 접근할 때, 시간 복잡도를 생각하지 않고 접근했었습니다. 따라서 아래와 같이 코드를 작성하였는데

#include <stdio.h>

int sum=1;

int f(int a){
	if(a < 3){
		return 1;
	}
	return f(a-1) + f(a-2) % 10009;
}

int main(){
	
	int a;
	scanf("%d", &a);
	printf("%d\n", f(a));
	
	return 0;
}

시간 초과가 뜨는 대참사가 나버렸다. 따라서 해당 문제를 해결하기 위해 열심히 구글링을 해본 결과

메모리제이션이라는 개념을 알아내었습니다. 

 

따라서 메모리제이션 기법을 이용하여 피보나치 수열 알고리즘을 다시 작성한 결과 아래와 같이 코드를 완성 하였습니다.

#include <stdio.h>

int arr[201];

int f(int a){
    if(a < 3)
        return 1;
    if(arr[a] != 0)
        return arr[a];
    return arr[a] = (f(a - 1) + f(a - 2)) % 10009;
}

int main(){
    int a;
    scanf("%d", &a);
    printf("%d", f(a));

    return 0;
}

 

 

우선 계산한 값을 담을 arr 배열을 선언해주고,  계산한 결과를 해당 배열에 저장해줍니다. 만일 해당 배열 값이 이미 계산한 적이 있는 값이라면 해당 값을 그대로 return해줍니다. 만일 해당 배열 값이 계산한 적이 없는 값이라면 계산하고 배열에 저장해줍니다. 따라서 시간 복잡도를 매우 획기적으로 줄일 수 있었습니다. 

 

 

 

 

 

 

 

참고 블로그 : https://wondytyahng.tistory.com/entry/memoization-%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

https://ssminji.github.io/2020/02/05/the-cake-thief/

[알고리즘] Memoization(메모이제이션) 꿀이해