[BOJ 2748] 백준 피보나치 수 2 풀이 - C++ (dynamic programming)

사용언어 :  C++

 

 

문제풀이

 * 핵심 : dynamic programming 을 이용해 작성하기 (+memoization)

1 . 단순히 재귀를 이용해 작성했을 때 (long long 인 이유는 n이 커질수록 값이 기하급수적으로 커지기 때문)

#include <iostream>
using namespace std;
int n;

long long fibonacci(long long x) {
	if (x == 1)return 1;
	if (x == 2)return 1;
	return fibonacci(x - 1) + fibonacci(x - 2);
}
int main() {
	cin >> n;
	cout << fibonacci(n);
}

물론 잘 작동한다. 그러나 n에 50을 입력해보자. 값이 출력이 되지만 시간이 오래걸린다. 그 이유는 이 때 시간복잡도가 O(2^n) 이기 때문이다.(fibonacci 함수에서 값을 return 할 때마다, fibonacci함수를 두 번 호출함!)

 

 

이를 해결하기 위해

2. Dynamic Programming을 사용 (+memoization) : O(n)

---

우선, Dynamic Programming(동적 계획법) 이란? 

: 문제를 작게 쪼개서 작은 문제부터 하나하나 해결한 해를 통해 모아서 큰 문제를 해결하는 방법

(재귀함수가 top-down방식일 때, 동적계획법은 bottom-up방식.)

---

작은 문제부터 차근차근 하나씩 올라가며 문제를 해결한다 -> 값을 저장하는 '배열' 을 사용

long long arr[100];

작은 수부터 값을 구할 때마다 arr배열의 해당 index에 값 대입. (값을 return 할 때 따로 함수를 호출 후 계산할 필요 없음) -> O(n)

 

전체코드

#include <iostream>
using namespace std;
int n;
long long arr[100];

long long fibonacci(long long x) {
	if (x == 1)return 1;
	if (x == 2)return 1;
	if (arr[x] != 0)return arr[x];
	return arr[x] = fibonacci(x - 1) + fibonacci(x - 2);
}
int main() {
	cin >> n;
	cout << fibonacci(n);
}

 

---

총평

알고리즘을 아직 제대로 배워본 적 (공부해본 적)이 없어서 dynamic programming 관련 문제는 처음 풀게 되었다. dynamic programming 조차 뭔지 몰라 우선 개념을 익히려고 유튜브 21강 - 다이나믹 프로그래밍(Dynamic Programming) [실전 알고리즘 강좌(Algorithm Programming Tutorial) #21] (동빈나) 를 시청했다. 그런데 예시로 딱 피보나치를 이용한, 나아가 memoization까지 사용한 예시를 알려주셔서 거의 그대로 코딩했다고 해도 과언이 아니다. 따라하려고 따라한 건 아닌데... 워낙 코드가 간결해서 .. 그럼에도 불구하고 몇 번 틀렸는데 그 이유는 값 범위를 신경쓰지 않았기 때문.. 무작정 int로 때려박았기 때문에 범위를 넘어버렸기 때문(음수가 나왔음) long long으로 수정하니 맞았다!

---

문제 출처

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

2748번: 피보나치 수 2

 

참고 

https://twpower.github.io/58-fibonacci-by-using-dp-and-recursion