서론
본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다.
대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다.
문제
Baekjoon 2748번 - 피보나치 수 2:
https://www.acmicpc.net/problem/2748
2748번: 피보나치 수 2
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
해법
이 문제는 정수 n이 주어질때 n번째 피보나치 수를 출력하는 문제이다. "피보나치"라는 단어를 보고 벌써 떠올리는 사람도 있겠지만 이번 문제는 "동적계획법(Dynamic Programing)"(이하 DP)을 사용하여 풀면 된다.
DP를 적용하는 방법은 크게 "Top-Down", "Bottom-Up"이 있다. Top-Down은 재귀함수를 이용하여 구현하게 되는데, 이로인해 콜스택 오버플로우가 발생할 수 있다. 하지만 Bottom-Up은 반복문을 사용하여 구현하기 때문에 이러한 문제를 해결 할 수 있고 시간복잡도 또한 줄일 수 있다.
DP에 대한 자세한 설명은 다른 문서들에도 자세히 설명되어있으니 참고자료에 있는 링크를 참고하기 바란다.
풀이
참고자료
위키피디아 - 동적계획법:
https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
동적 계획법 - 위키백과, 우리 모두의 백과사전
수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분
ko.wikipedia.org
'SW > Baekjoon' 카테고리의 다른 글
| [Baekjoon 문제풀이] 4153 - 직각삼각형 (Python 3) (0) | 2022.01.04 |
|---|---|
| [Baekjoon 문제풀이] 9461 - 파도반 수열 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 2581 - 소수 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 2609 - 최대공약수와 최소공배수 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 1085 - 직사각형에서 탈출 (Python 3) (0) | 2022.01.04 |