내 맴

문제 ) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net [ 풀이 ] 문제를 읽어보고 그냥 재귀함수를 사용해서 문제를 풀되 fib(0)과 fib(1)이 얼마나 호출되는지 알아내게끔 코드를 변경하라는 건줄 알았다. 문제를 풀고 제출해보니 시간초과가 되어버렸다. 그래서 시간초과를 하지 않는 새로운 방법으로 문제를 풀어보았다. 바로 0과 1 호출 횟수에 대한 List를 만들어 Dynamic Programming으로 문제를 푸는 것이다 예를 들어 , fib(3)= fib(2)+fib(1) = fib(0) + fib(1) + fib(1) 로 fib(..

문제 ) https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)�� www.acmicpc.net [ 풀이 ] 피보나치 수열의 경우 재귀함수를 사용하면 안되는 대표적인 문제이다. 재귀함수를 사용하게 되면 중복호출이 매우 많아지기 때문이다. 재귀 알고리즘을 이용해 피보나치 수를 구하려면 의사코드는 이런식으로 작성된다 이때, Fib함수가 얼마나 호출되는지 보기 위해서 그래프로 그려보았다. 재귀함수를 이용해 피보나치 수를 구하면 그래프의 분홍색 동그..