[C언어] 백준 1003 : 피보나치 함수
생각의 흐름
이번에는 동적 계획법이라는 파트이다. 당연히 처음 들어보기에 바로 구글링으로 어떤건지 찾아보았다.
https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP 여기에서 도움을 받았다.
간단하게 말하자면, 기본적으로 피보나치로 예를 드는데, 중복되는 계산을 피하자! 이거다.
그걸 메모이제이션이라고 하는데, 크게 두가지 방법을 사용하나보다.
- 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];
}
- 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으로 한다.
Author And Source
이 문제에 관하여([C언어] 백준 1003 : 피보나치 함수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmainsain/C언어-백준-1003-피보나치-함수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)