https://www.acmicpc.net/problem/2747
2747번: 피보나치 수
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
c++로 백준 2747번 문제를 풀어보겠다.
<문제 풀이>
처음에 작성한 코드는 다음과 같다.
맞을 거라고 생각했지만 '시간 초과' 라고 떴다.
알고리즘의 시간복잡도를 해결해야했다.
이 부분은 서치를 통해 해결했다.
이를 해결하기 위해서는 "동적 계획법"을 사용해야만 했다.
DynamicProgramming(동적계획법)"은 Memoization을 이용해 문제를 푸는 방식이다.
Memoization이란 함수를 쭉 호출해가는 과정에서 해당하는 n에 대해 최초로 답을 구했을 때, 어딘가에 답을 적어둔다면 다시 만났을 때 그 답을 활용 할 수 있으므로 더는 전개할 필요가 없게 되는 기법이다.
따라서 다시 작성한 코드는 다음과 같다.
피보나치 수를 구해 배열에 저장하는 과정을 추가했다.
그리고 원하는 피보나치 수가 이미 배열에 계산되어 저장되어 있다면 더이상 계산을 하지 않고 배열에 저장된 값을 리턴하며 시간복잡도를 줄였다.
'C++' 카테고리의 다른 글
| [백준 알고리즘] 1325번 : 효율적인 해킹, c++ (0) | 2022.05.15 |
|---|---|
| [백준 알고리즘] 2444번 : 별 찍기 - 7, c++ (0) | 2022.05.14 |
| [백준 알고리즘] 4447번 : 좋은놈 나쁜놈, c++ (0) | 2022.05.12 |
| [백준 알고리즘] 1764번 : 듣보잡, c++ (0) | 2022.05.11 |
| [백준 알고리즘] 10824번 : 네 수, c++ (0) | 2022.05.10 |