[C언어] 백준 1003 : 피보나치 함수

생각의 흐름

이번에는 동적 계획법이라는 파트이다. 당연히 처음 들어보기에 바로 구글링으로 어떤건지 찾아보았다.
https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP 여기에서 도움을 받았다.
간단하게 말하자면, 기본적으로 피보나치로 예를 드는데, 중복되는 계산을 피하자! 이거다.
그걸 메모이제이션이라고 하는데, 크게 두가지 방법을 사용하나보다.

1. TOP-DOWN

int fiboData[100] = {0,};

int fibo(int n)
{
  if (n <= 2) 
    return 1;
  if (fiboData[n] == 0)
    fiboData[n] = fibo(n - 1) + fibo(n - 2);
  return fiboData[n];
}

2. BOTTOM-UP

int fibo(int n)
{
  fibodata[0] = 0;
  fiboData[1] = 1;
  for (int i = 2; i <= n; i++)
    fiboData[i] = fiboData[i - 1] + fiboData[i - 2];
  return fiboData[n];
}

이렇게 기억하면서 내려가고, 올라간다. 이 방법을 익혀놓자.

먼저, 위 식을 생각안하고, 내 방식대로 풀어보기로 했다.

내가 푼 코드 (시간초과)

#include <stdio.h>

int counta = 0;
int countb = 0;

int fibo(int n)
{
	if (n == 0)
	{
		counta++;
	}
	else if (n == 1)
	{
		countb++;
	}
	else return fibo(n - 1) + fibo(n - 2);
}

int main()
{
	int t, n, i;
	scanf("%d", &t);
	i = 0;
	while (i < t)
	{
		scanf("%d", &n);
		fibo(n);
		printf("%d %d\n", counta, countb);
		counta = 0;
		countb = 0;
		i++;
	}
}

피보나치 재귀 돌리면서 0과 1을 프린트하는 방법이다.

기억하면서 돌아간게 아니기에 시간초과를 받았다. 당연하지만 n이 22만 되어도 정말 많은 재귀를 돌리기때문에 시간초과가 난다.

수정한 코드

#include <stdio.h>

int main()
{
	int i, n, t;
	int fibo[41] = {0, 1};
	scanf("%d", &t);
	i = 2;
	while (i < 41)
	{
		if (fibo[i] == 0)
		{
			fibo[i] = fibo[i - 1] + fibo[i - 2];
		}
		i++;
	}
	i = 0;
	while (i < t)
	{
		scanf("%d", &n);
		if (n == 0)
			printf("1 0\n");
		else 
			printf("%d %d\n", fibo[n - 1], fibo[n]);
		i++;
	}
}

bottom-up으로 다 세주고, 출력을 진행했다.
https://wtg-study.tistory.com/5 여기에서 아이디어를 얻었었다.

다른 사람 코드

#include <stdio.h>
 
void fibonacci(int N)
{
    int last, current, result;
    current=1, last = result = 0;
    int i;
    for (i = 0; i <=N; i++)
    {
        last = current;
        current = result;
        result = last + current;
    }
    printf("%d %d\n", last, current);
}
int main()
{
    int N,M;
    int i;
    scanf("%d", &N);
    for (i = 0; i < N; i++)
    {
        scanf("%d", &M);
        fibonacci(M);
    }
}

https://evga7.tistory.com/64
이렇게 반복문으로 직접 세는 방법도 있다. 이것도 bottom-up으로 한다.