프로그래머스 Level 2 : 피보나치 수 C언어

▶문제 : 코딩 테스트 연습 - 피보나치 수 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 피보나치 수

 

▶코드 작성(개선 코드 있음)

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int memo[100000];//메모할 배열

int fibo(n)
{
    if (n == 0) return 0;
    if (memo[n] != 0) return memo[n];//메모배열에 있다면 배열값 반환
    else return memo[n] = (fibo(n - 1) + fibo(n - 2)) % 1234567;//메모배열에 없으면 재귀함수 호출
}

int solution(int n)
{
    memo[1] = 1;
    return fibo(n) % 1234567;
}

메모이제이션으로 피보나치 수를 구하였는데 더욱 빠른 방법이 있었다.

 

▶개선 코드

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int n)
{
    int sum;
    int num1=0,num2=1;

    for(int i=2;i<=n;i++)//n까지 반복
    {
        sum=(num1+num2)%1234567;//F(n-2) + F(n-1)
        num1=num2;//다음 수를 구하기 위해 F(n-1)값인 num2를 대입
        num2=sum;//마찬가지로 다음 수를 구하기위해 sum을 대입
    }
    return sum;
}

 

▶해석

F(n-2)는 num1, F(n-1)는 num2로 유지하면서 둘을 더하여 F(n)을 구하였다.

메모이제이션은 if문과 재귀 함수로 시간이 더 걸리는 듯하다.