[ C++ ] #24416 알고리즘 수업 - 피보나치 수 1

알고리즘시간에 배운 동적프로그래밍 문제를 하나 가져와봤다.

 

의사코드를 한번 보면 재귀호출은 들어온 숫자(n)이 1이나 2가 아니라면

n-1과 n-2를 인자로 재귀호출하여 더해준다.

 

만약 6이 들어온다면

f(6) → f(5) + f(4) → ( f(4)+f(3) ) + ( f(3)+f(2) )

→ ( ( f(3)+f(2) ) + ( f(2)+f(1) ) ) + ( ( f(2)+f(1) )+1 )

→ ( ( ( f(2)+f(1) )+1 ) + ( 1+1 ) ) + ( (1+1 )+1 )

→ ( ( ( 1+1 )+1 ) + 2 ) + 3 → 8

 

동적프로그래밍 의사코드를 보면

인자로 들어온 n만큼 배열을 만들어서 인덱스 1,2, 에는 1을 넣어주고

나머지 인덱스에는 앞에 두자리를 더한 값을 넣어준다.

 

하지만 '피보나치 수'를 구하는 것이 아니라 각 코드가 몇번 실행되었는지를 출력하는 것이기 때문에

횟수를 세주는 변수 두개를 전역변수로 선언하였다.

 

---

 

#include <iostream>

using namespace std;

int re, di;

int fib(int n) { //재귀호출
	if (n == 1 || n == 2) {
		re++;
		return 1;
	}
	else return (fib(n - 1) + fib(n - 2));
}

int fibonacci(int n) {  //동적프로그래밍

	int* f = new int[n];

	f[0] = 1;
	f[1] = 1;

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

}

int main() {

	int num;
	cin >> num;

	fib(num);
	fibonacci(num);

	cout << re << " " << di;

}

 

동적프로그래밍의 기본인 치보나치 수를 해보았다.

다른 예제들도 더 풀어보며 애매하게 잡혀있는 동적프로그래밍 개념을 

더 잡아봐야겠다