문제 링크https://www.acmicpc.net/problem/17175  문제혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 문제를 만들려 한다.int fibonacci(int n) { // 호출 if (n 위와 같이 코딩하였을 때 fibonacci(n)를 입력했을 때에 fibonacci 함수가 호출되는 횟수를 계산해보자.  입력fibonacci 함수에 인자로 입력할 n이 주어진다. (0 ≤ n ≤ 50)  출력fibonacci 함수가 호출된 횟수를 출력한다.출력값이 매우 커질 수 있으므로 정답을 1,000,000,007 로 나눈 나머지를 출력한다.   통과한 답안..

문제 링크https://www.acmicpc.net/problem/9711  문제피보나치 수열은 아래와 같이 표현된다.1, 1, 2, 3, 5, 8, 13, 21, 34, ...각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라.   입력첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다.각 테스트 케이스는 정수 P와 Q가 주어진다.  출력각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다.x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다.  제한1 ≤ P ≤ 10,0001 ≤ Q ≤ 2,000,000,000   통과한 답안using System.Numer..

문제 링크https://www.acmicpc.net/problem/6571  문제피보나치 수의 정의는 다음과 같다.f1 := 1f2 := 2fn := fn-1 + fn-2 (n ≥ 3)두 수 a와 b가 주어졌을 때, 구간 [a, b]에 포함되는 피보나치 수의 개수를 구하는 프로그램을 작성하시오.  입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 음이 아닌 두 정수 a와 b로 이루어져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다. (a ≤ b ≤ 10100) 두 수 a와 b는 불필요한 0으로 시작하지 않는다.  출력각 테스트 케이스에 대해서, a ≤ fi ≤ b 인 피보나치 수 fi의 개수를 출력한다.   통과한 답안using System.Numerics;namespace _..

알고리즘시간복잡도와 공간복잡도가 무엇인지 설명해주실 수 있을까요?더보기시간복잡도 시간 복잡도는 문제를 처리하는데 걸리는 시간을 의미합니다.즉, 문제를 푸는데 걸리는 연산의 속도와 연결되는 것으로입력 값에 따라서 수행하는 연산의 수를 나타냅니다.이는 주로 BigO 표기법을 사용하여 표기되며, 대표적인 시간 복잡도는 아래와 같습니다.O(1), O(n), O(log n), O(n log n), O(n^2) 공간 복잡도는 문제를 처리하는데 필요한 공간의 크기를 의미합니다.즉, 문제를 푸는데 필요한 데이터를 저장하는 공간과 연결되는 것으로,입력 값에 따라서 필요한 메모리를 나타냅니다.이를 BigO 표기법으로 표현하면 O(1), O(n), O(n^2) 등으로 표현할 수 있습니다. 시간복잡도가 높은 경우 취할 수 있..

문제 링크https://www.acmicpc.net/problem/1788  문제수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다.하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n > 1인 경우에만 성립하는 F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. 예를 들어 n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다.n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하시오. n은 음수로 주어질 수도 있다.  입력첫째 줄에 n이 주어진다. n은 절댓값이..

문제 링크https://www.acmicpc.net/problem/14495  문제피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!  입력자연수 n(1 ≤ n ≤ 116)이 주어진다.  출력n번째 피보나치 비스무리한 수를 출력한다.   통과한 답안using System.Numerics;namespace _14495{ internal class Program { static Dictionary Fibo = new Dictionary()..