Search

BOJ 10870 피보나치 수 5

태그
재귀
수학
구현
URL
한 줄 요약 똑같은 값을 여러 번 구한다면, 배열에 저장하여 재사용하는 것이 좋다. (메모이제이션 기법)
www.acmicpc.net
https://www.acmicpc.net/problem/10870
%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%205.py
Problem

문제 설명

•
n번째 피보나치 수를 구하는 문제

예제 입력/출력

•
입력1
10
Python
복사
•
입력1
55
Python
복사

제약 조건

•
0≤n≤200 ≤ n ≤ 20

문제 풀이

•
피보나치 수를 구하는 공식을 코드로 구현하면 되며, 이는 반복문이나 재귀함수를 통하여 구현할 수 있다.
•
반복문을 이용한 피보나치 구하기
◦
풀이1 - O(n)O(n)
•
재귀함수를 이용한 피보나치 구하기
◦
메모이제이션 사용 X
▪
풀이2 - 상한 O(2n)O(2^n)
◦
메모이제이션 사용 O
▪
풀이3 - O(n)O(n)

풀이 코드

풀이1 : 반복문 + 메모이제이션
풀이2 : 재귀함수
풀이3 : 재귀함수 + 메모이제이션