12. codeup 2601 : 피보나치 수열 문제 해결

출처 <코드업 사이트>

 n번째에 해당하는 피보나치 수를 구하는 문제입니다. 

 

피보나치 수열의 개념을 알고리즘으로 표현하여 코드를 구현하면 될 것 같네요. 재귀함수를 이용하였습니다.

#include <stdio.h>

int f(int n){
    if(n<=1) return n;      //1항은 1 반환
    else return f(n-1)+f(n-2);   //항들의 합
}

int main(){
    int n;   //수 입력
	scanf("%d", &n);

	printf("%d",f(n));  //결과 출력
}

C로만 구현해보기 아쉬워서 파이썬으로도 구현해 보았습니다.

a={}  //리스트 선언

def f(n):
    if n<=1:     //1항은 1 반환
        return n
    if n in a:   //리스트에 이미 저장된 수 반환
        return a[n]
    else:
        a[n]=f(n-1)+f(n-2)    //리스트에 계산값 넣기
        return a[n]

n= int(input())  //입력

result= f(n)   
print(result)  //결과 출력

 

 

파이썬으로 구현할때 C로 구현할때와 같은 방식으로 재귀함수만을 사용하였더니 시간초과가 났습니다. 이 문제를 해결하기 위하여 메모이제이션을 사용하였는데요. 리스트를 만들어서 리스트에 이미 그 수에 해당하는 값이 있으면 그 값을 반환하고 리스트에 없는 값만 계산하는 방식으로 시간을 줄일 수 있었습니다.

 

읽어주셔서 감사합니다.