[Python]알고리즘/백준
[다이나믹 프로그래밍] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2
[백준] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 (한줄평) 다이나믹 프로그래밍으로 해결할 수 있었던 문제! 2가지 문제는 n번째 피보나치수를 구하는 문제로 두 문제의 차이는 n의 범위다. 2747번은 n의 범위가 45이하 자연수이고 2748번은 n의 범위가 90이하 자연수이다. 일단 두 문제 모두 일반 재귀로 피보나치 수를 구하려면 시간복잡도가 (2**n)으로 45이면 2**45(약 10**12), 90이면 2**90(약 10**27)으로 시간 초과가 나올 것이다. 그러므로 dp로 풀어야한다! (풀이1) 반복문 이용 풀이 시간: 5분 이내 1) 문제 해결 아이디어 2) 소스코드 n = int(input()) # 1. 45이하 자연수, 2. 90이하 자연수 d = [0] * (n + 1..
