Baekjoon - 피보나치 함수

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

 

문제의 조건은 N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하는 것이다. 그리고 제한 시간이 0.25초 라는 것을 명심해야 한다.

 

문제에서 주어진 대로 재귀 함수로 구현한다면 시간초과가 뜬다. 

 

찾아보니깐 방법이 두가지가 있었다.

1. 메모이제이션

2. DP(동적프로그래밍)

 

이 글에서는 메모이제이션에 대해서 설명하겠다.

 

피보나치란?

피보나치 수열은 F(n) = F(n-1) + F(n-2)의 형태로, 이전 두 수의 합이 현재 수가 되는 수열입니다.

 

• 기본 값: F(0) = 0, F(1) = 1
• 예시: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

재귀로 구현했을 때 문제점

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

 

 

• 중복 계산 문제: 같은 값을 여러 번 계산하게 됩니다.
• 예를 들어 F(5)를 계산할 때:
  • F(4)와 F(3)을 계산
  • F(4)는 다시 F(3)와 F(2)를 계산
  • F(3)이 여러 번 중복 계산됨
• 시간 복잡도: O(2^n)으로 매우 비효율적
• 해결 방법 메모이제이션

 

 

메모이제이션?

 

한 번 계산한 값을 배열에 저장해두고 재사용하는 방식이다.

• 중복 계산을 피할 수 있어 효율적
• 시간 복잡도: O(n)으로 크게 개선

int zero[41]; // 0이 출력되는 횟수를 저장하는 배열
int one[41];  // 1이 출력되는 횟수를 저장하는 배열

void count_fibonacci() {
    // 기본 케이스 초기화
    zero[0] = 1; // f(0)을 호출하면 0이 1번 출력
    one[0] = 0;  // f(0)을 호출하면 1은 0번 출력
    
    zero[1] = 0; // f(1)을 호출하면 0은 0번 출력
    one[1] = 1;  // f(1)을 호출하면 1이 1번 출력
    
    // 다이나믹 프로그래밍으로 값 계산
    for(int i = 2; i <= 40; i++) {
        zero[i] = zero[i-1] + zero[i-2]; // i번째 수에서 0이 출력되는 횟수
        one[i] = one[i-1] + one[i-2];    // i번째 수에서 1이 출력되는 횟수
    }
}

 

 

메모이제이션이 사용된 부분과 원리

• zero[]와 one[] 배열 자체가 메모이제이션을 구현한 것이다.
• 각 배열은 특정 n값에 대해 0과 1이 각각 몇 번 출력되는지를 저장한다.
• 한 번 계산된 값은 배열에 저장되어 있어 재사용된다.
• 피보나치의 특성을 이용해 현재 값은 이전 두 값의 합으로 계산된다.

예를 들어, f(3)의 경우:

• zero[3] = zero[2] + zero[1]
• one[3] = one[2] + one[1] 이런 식으로 이전에 계산해둔 값들을 재사용하여 새로운 값을 계산한다.

 

 

메모이제이션의 작동 방식

1. 첫 번째 계산

   memo[0] = 0  // 기본값
   memo[1] = 1  // 기본값

   
   
2. 값을 계산하고 저장

   // F(2) 계산
   memo[2] = memo[1] + memo[0]  // 1 저장
   
   // F(3) 계산
   memo[3] = memo[2] + memo[1]  // 2 저장
   
   // F(4) 계산
   memo[4] = memo[3] + memo[2]  // 3 저장

   
   
3. 저장된 값 재사용
   • F(3)이 다시 필요할 때는 계산하지 않고 memo[3]에서 바로 가져옴
   • 마치 계산 결과를 메모장에 적어두고 필요할 때 다시 보는 것과 같음

간단한 비유를 들자면:

• 메모이제이션이 없을 때: 매번 1+1을 계산하는 것
• 메모이제이션이 있을 때: 1+1=2라는 것을 메모해두고 다음에는 계산하지 않고 2를 바로 사용

예제 코드:

int memo[100] = {0}; // 결과를 저장할 배열

int fibonacci(int n) {
    // 이미 계산된 값이 있으면 바로 반환
    if (memo[n] != 0) return memo[n];
    
    // 기본 케이스
    if (n <= 1) return n;
    
    // 계산하고 메모에 저장
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
}