백준 알고리즘 2748번 피보나치 수 2 (C언어)

브론즈Ⅰ

 

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

2748번: 피보나치 수 2

 

 

풀이 방법

 

피보나치 수열은 첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때, 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다. 즉, 아래의 표처럼 진행된다.

0	1	2	3	4	5	6	7	8	9
0	1	1	2	3	5	8	13	21	34

피보나치 수열은 보통 재귀함수열을 이용해 풀지만, 재귀함수로 풀 경우 시간이 많이 걸린다. 따라서 보통은 재귀함수와 메모이제이션을 함께 이용해 문제를 해결한다. 

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

이 문제의 경우 n이 90일 경우 Fibonacci(90)까지 계산해야한다. 또한, Fibonacci(90)은 2,880,067,194,370,816,120이므로, 이전 값을 기억할 memo 배열과 결과를 출력할 result 변수를 모두 long long 자료형으로 정의해야 한다는 점을 주의해야한다.

내 코드

#pragma warning(disable:4996)
#include <stdio.h>
 
long long fibonacci(int n, long long* memo);
 
int main() {
    
    int n;
    long long result;
    long long memo[91] = { 0, 1, };
 
    scanf("%d", &n);
 
    result = fibonacci(n, memo);
 
    printf("%lld\n", result);
    
    return 0;
}
 
long long fibonacci(int n, long long* memo) {
    if (memo[n] != 0 || n == 0)
        return memo[n];
    else
        return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
}

 

 

코드설명

반응형

1   | scanf 함수를 사용할 때 경고창을 띄우지 않도록 하는 전처리 지시문이다.

2   | scanf, printf 함수를 사용하기 위한 전처리 지시문이다.

4   | 피보나치 수열을 계산하기 위한 함수를 정의하였다. 여기서 피보나치 수열의 90번째에 해당하는 수까지 계산해야 되기 때문에 long long 형태로 함수의 return 값을 정의하였다.

5   | 배열을 역순으로 뒤집는 함수를 사용하기 위해 선언하였다. (60~69)

9~10   | 피보나치 수열의 90번째에 해당하는 수까지 계산해야 되기 때문에 long long 형태로 result 변수와 memo 배열을 정의하였다.

16 |  long long 자료형의 출력을 위해 서식지정자를 %lld의 형태로 출력하였다.

22~23 | 피보나치 수열의 n번째에 해당하는 수가 memo[n] 안에 저장되어 있을 경우, 혹은 n이 0일 경우 memo[n]에 저장되어 있는 값을 return하는 코드이다.

24~25 | 피보나치 수열의 n번째에 해당하는 수가 memo[n] 안에 저장되어 있지 않을 경우 원래의 피보나치 수열을 구하는 과정처럼 n-1번째 수와 n-2번째 수의 합을 구해서 memo[n]에 저장한 후 그 값을 return하는 코드이다.

 

 

느낀점

 

- 재귀함수를 공부한 후, 재귀함수의 대표적인 예시인 피보나치 수열을 재귀함수로 구현할 수 있다면 쉽게 풀 수 있다.

- 재귀함수와 재귀함수를 이용해 피보나치 수열을 구현할 수 있게된 후, 피보나치 수열의 n의 값이 커질 경우 계산시간이 기하급수적으로 늘어나는 점을 체감하고, 이에 대한 해결방안으로 '메모이제이션' 이라는 방법을 찾고, 활용하여 문제를 풀 수 있었다.