백준 2748번 C언어 풀이

https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

저번에는 피보나치 수열의 일반항으로 풀어보았다. (https://codejin.tistory.com/116)

 

이번에는 다른 방법으로 풀어보자. 이번에는 dp로 풀어보았다. 그중에서도 메모이제이션을 통해 접근해보았다.

 

메모이제이션이란 컴퓨터프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. (출처 : 위키백과)

 

기존의 일반적인 재귀방식의 피보나치함수가 느린 이유는, 숫자가 늘어날수록 지수적으로 연산횟수가 늘어나기 때문이다. 게다가 동일한 연산도 과다하게 반복하게 된다. 이를 해결할 방법이 메모이제이션이다.

 

수행했던 연산이 아니라면, 기존의 방식으로 접근하되, 어느순간 연산했던 과정이 나오는 경우, 이를 기록해두었던 값을 가져옴으로써 연산횟수를 줄인다.

 

#include <stdio.h>
#include <math.h>

#define ULL unsigned long long
#define SIZE 91

ULL fibo(int n) {
    static ULL fiboarr[SIZE] = {0,1};
    if (n <= 1) return n;
    else if (fiboarr[n]) return fiboarr[n];
    else {
        fiboarr[n] = fibo(n-1) + fibo(n-2);
        return fiboarr[n];
    }
}

int main () {
    int n;
    scanf("%d", &n);
    printf("%lld", fibo(n));
}

 

피보나치 수열에서도 배울건 참 많다.