BOJ 백준 [2748] 피보나치 수
2019. 9. 12. 00:02ㆍAlgorithm/ 백준 온라인 저지
일반적으로 피보나치 수를 이용하여 문제를 해결하려고 해보면,
|
1
2
3
4
5
6
7
|
int getFibo(int n) {
if (n<=1) {
return n;
}
return getFibo(n-1) + getFibo(n-2);
}
Colored by Color Scripter
|
위와 같이 간단한 재귀함수를 생각해낼 것이다. 하지만, 위의 코드의 경우 n의 최댓값이 90이므로,
주어진 n에서 최댓값이 주어질 경우 해당 피보나치 수는 int의 최댓값을 넘을 것이다.
--> long long 자료형을 사용해 주자.
그리고 시간 복잡도의 경우 2^n이므로 최악의 경우 2^90 = 1,237,940,039,285,380,274,899,124,224 이므로,
1초의 시간을 넘어 서게 된다. 위의 경우, 어떻게 문제를 해결해야 할까?
IDEA 1
for 문으로 탐색해서 피보나치 값을 구해보자.
|
1
2
3
4
5
6
7
8
9
10
|
if(n <= 1) {
printf("%d", n);
} else {
for(int i=2 ; i <= n ; i++) {
ans = prev_1 + prev_2;
prev_2 = prev_1;
prev_1 = ans;
}
printf("%lld",ans);
}
|
위와 같이 for문을 이용해서 문제를 해결한다면 O(n)의 시간내에 해결이 가능하다.
IDEA 2
만약 재귀함수로 문제를 해결하고 싶다면, 메모제이션 기법을 이용하여 문제를 해결해보자.
메모제이션 기법을 사용하면 반복적으로 사용되는 데이터가 도출되기까지 연산을 하는 과정이있다면, 이를 저장해 놓음으로서 여러번 반복적인 연산을 하지 않게 할 수 있다.
|
1
2
3
4
5
6
7
8
|
unsigned long long fibo[100];
unsigned long long Get_Fibo(int n) {
if (n <= 1) return fibo[n];
if (fibo[n] != -1)return fibo[n];
fibo[n] = Get_Fibo(n - 1) + Get_Fibo(n - 2);
return fibo[n];
}
Colored by Color Scripter
|
만약, fibo배열이 -1로 초기화 되어 있다고 생각해보자. 이미 연산을 한 값에 대해서는 기록된 값을 사용하면 되므로 위에서 여러번 반복적으로 연산하여 2^n의 시간이 들게 한 것을 n의 시간으로 줄일 수 있다.
'Algorithm > 백준 온라인 저지' 카테고리의 다른 글
| BOJ 백준 [11403] 경로 찾기 (0) | 2019.09.18 |
|---|---|
| BOJ 백준 [2156] 포도주 시식 (0) | 2019.09.18 |
| BOJ 백준 [2805] 나무 자르기 (0) | 2019.09.04 |
| BOJ 백준 [2003] 수들의 합 2 (0) | 2019.09.03 |