[Baekjoon] 24416번: 알고리즘 수업 - 피보나치 수 1

https://www.acmicpc.net/problem/24416

24416번: 알고리즘 수업 - 피보나치 수 1

 

---

 

문제 해결 과정

착안

문제에서 주어진 의사 코드를 그대로 구현하여, 피보나치 수열(Fibonacci sequence)의 \(n\)번째 항을 구하기 위한 재귀 호출(recursive call, recursion)을 통한 계산에서의 코드 1의 실행 횟수와 동적계획법(dynamic programming)을 통한 계산에서의 코드 2의 실행 횟수를 각각 출력한다.

* 참고) 경우에 따라, 피보나치 수열의 처음 두 항을 0 과 1로 간주하는 곳도 있다.

 

구현

문제에서 의사 코드를 제공했기 때문에 그대로 구현하기만 하면 돼서 코드적으로 어려운 점은 없었다. 단, 원리적으로 생각해보면 일일이 재귀적으로 직접 호출하지 않아도 코드 1의 실행 횟수를 알 수 있다. 재귀를 통한 계산에서 피보나치 수열에 대한 점화식을 이용해 \(1\)번째 항 또는 \(2\)번째 항의 값만을 사용하여 연산할 수 있을 때까지 재귀적으로 함수를 호출하여 항의 번호를 낮춰간다. 이때 코드 1의 실행 횟수는 return 1;을 실행하는 횟수와 같으므로 결국 1의 값을 몇번 더하는 지를 세는 것과 같다. 따라서, 피보나치 수열의 \(n\)번째 항의 값이 곧 코드 1의 실행 횟수이다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

unsigned int f[41] = { 0, 1, 1, };
unsigned int count1 = 0;
unsigned int count2 = 0;
using namespace std;

// 위에서 언급했듯이, 해당 함수를 직접 돌리지 않고
// 아래의 fibonacci() 만 사용해도 코드 1의 실행 횟수를 알 수 있다.
// 즉 count1 == fibonacci(N) 이므로, fib 함수를 호출하지 않고 출력 부분을
//
// cout << fibonacci(N) << " " << count2 << "\n";
//
// 와 같이 수정하여 제출하면 0 ms가 나온다.
// 공부 목적으로는 그냥 재귀 호출을 직접 해서 결과를 확인해보는 것이 더 좋다고 생각한다.
int fib(int n)
{
	if (n == 1 || n == 2)
	{
		count1++;
		return 1;
	}
	else
		return (fib(n - 1) + fib(n - 2));
}

int fibonacci(int n)
{
	for (int i = 3; i <= n; i++)
	{
		f[i] = f[i - 1] + f[i - 2];
		count2++;
	}
	return f[n];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;

	fib(N);
	fibonacci(N);
	cout << count1 << " " << count2 << "\n";

	return 0;
}

 

실행 결과

위의 결과는 재귀적으로 함수를 호출하지 않고 이론적으로 재귀 호출 횟수를 구한 결과임(구현 코드의 주석 참고).

 

이 문제에서 굳이 실행 속도를 0 ms로 만드는 건 하나도 중요한 건 아니지만 그냥 원리를 이용해서 꼼수를 써보았다...