[백준/BOJ] 24416번 알고리즘 수업 - 피보나치 수 1 (C)

개요

이 글은 백준 24416번 알고리즘 수업 - 피보나치 수 1 문제를 풀이한다.

요약

$n$을 입력받아 피보나치 수 재귀호출와 피보나치 수 동적 프로그래밍의 실행 횟수를 각각 출력하라.

입력 조건

$5 \leq n \leq 40$

분석

피보나치 수열은 다음과 같이 정의된다.

\[F_{n} = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F_{n-1} + F_{n-2} & \text{if } n \geq 2 \end{cases}\]

여기서 $F_{40} = 102,334,155$이므로, int 자료형으로 충분히 표현할 수 있다.

풀이

먼저 피보나치 수 재귀호출의 실행 횟수를 구해야 한다. 이는 $n = 3$부터 시작하여 직접 구해보면 된다. 구해보면 $2, 3, 5, 8, 13, …$와 같이 피보나치 수열의 특성을 가진다. 따라서 피보나치 수열의 $n$번째 항을 출력하면 된다.

다음으로, 피보나치 수 동적 프로그래밍의 실행 횟수를 구해야 한다. 이 역시 $n = 3$부터 시작하여 직접 구해보면 된다. 구해보면 $1, 2, 3, 4, 5, …$와 같이 증가하는 것을 확인할 수 있다. 따라서 $n - 2$를 출력하면 된다.

예시 답안

#include <stdio.h>

int fibonacci(int n) {
  int a[41];
  a[0] = 0;
  a[1] = 1;

  for (int i = 2; i <= n; i++) {
    a[i] = a[i - 1] + a[i - 2];
  }
  return a[n];
}

int main(void) {
  int n;

  scanf("%d", &n);
  printf("%d %d", fibonacci(n), n - 2);
  return 0;
}

원본 소스 코드는 Hiyabye/Baekjoon - 24416.c 에서 확인할 수 있다.

문제 해결 팁

재귀를 이용한 피보나치 수열 구현은 시간복잡도가 $\mathcal{O}(2^N)$으로 매우 느리다. 따라서 이 방법은 사용하지 않는 것이 좋다.

반복문을 이용한 DP를 사용하여 피보나치 수열을 구현하면 시간복잡도가 $\mathcal{O}(N)$으로 훨씬 빠르다.

마무리

도움이 되었다면 반응이나 댓글을 남겨주시면 감사하겠습니다.

추가적인 의견이나 피드백 또한 언제든지 환영입니다! :)