[C/C++] 코드업(codeup) 1916번 피보나치 수열 (Large) 그리고 메모이제이션

▽문제 바로가기

https://codeup.kr/problem.php?id=1916

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

---

입력

200이하의 자연수 N 입력

 

출력

N번째 피보나치 수를 출력하되, 10,009를 나눈 나머지 값을 출력

 

 

문제 풀이

 

먼저 일반적인 재귀 함수를 이용하여 N번째 피보나치를 출력하는 코드입니다.

#include <stdio.h>

int recur(int a){
	if(a==1||a==2){
		return 1;
	}
	else{
		return recur(a-1) + recur(a-2);
	}
}

int main(){
	
	int a, sum=1;
	scanf("%d", &a);
	int result = recur(a);
	printf("%d\n", result);
	
	return 0;
}

 

코드 진행 과정을 살펴보겠습니다. 예를 들어 5를 입력받으면 recur(5)는

					recur(5)
                    
			recur(4)			recur(3)
                
		recur(3)	recur(2)	recur(2)	recur(1)
        
	recur(2)	recur(1)

다시 recur(4)와 recur(3)을 호출할 것입니다. 그리고 1과 2가 나올 때까지 계속해서 함수를 호출할 것입니다. 1과 2를 만나면 리턴 값을 주면서 계속 위로 더해지고 결국 recur(4)까지의 결과값을 얻을 수 있고 왼쪽 트리의 계산은 끝이 납니다. 이제 오른쪽 트리의 recur(3)을 호출하여 또 1과 2를 만날 때까지 함수를 호출할 것입니다.

 

 

그런데 오른쪽 트리를 보니 왼쪽과 비슷한 부분이 있습니다.

 

 

빨간색 삼각형 부분이 일치합니다. 우리는 이미 왼쪽 트리에서 recur(3)을 호출하였고 recur(3)은 다시 recur(2)와 recur(1)을 호출해서 그 값을 알고 있습니다. 이미 알고 있는 값을 기억하여 저장해놓는다면 오른쪽트리 recur(3)은 굳이 필요 없는 함수 호출을 예방함으로써 속도를 높여줄 수 있습니다. 이것이 메모이제이션입니다.

만약, 입력 자연수 N이 더 크다면 이러한 부분이 더 큰 형태가 되겠죠.

 

문제에서 200 이하의 자연수 입력이라고 하였으니 201개의 배열을 만듭니다. 나머지는 주석을 참고하시면 될 것 같습니다.

그리고 문제에서 10009로 나눈 나머지를 출력하라고 하였으니 나누어줍니다.

 

#include <stdio.h>

int memo[201]={0};	//200보다 같거나 작다. 

long long int recur(int a){
	if(a==1||a==2){
		//recur(1), recur(2) 메모
		memo[a] = 1;
		return 1;
	}
	//메모한 값이 있다면 굳이 함수호출을 하지 않고 저장된 값 리턴
	if(memo[a]!=0){
		return memo[a];	
	}
	else{
		//메모해둔 값이 없다면 함수 호출하고 recur(3이상) 메모
		return memo[a] = (recur(a-1) + recur(a-2))%10009;
	}
}

int main(){
	
	int a;
	scanf("%d", &a);
	long long int result = recur(a);
	printf("%lld\n", result);
	
	return 0;
}