-
[Python] 백준 - 1003 피보나치 함수__Python/__Algorithm 2021. 12. 21. 12:37
# 백준 Silver3
# 1003 피보나치 함수
[문제]
링크 : https://www.acmicpc.net/problem/1003
[문제 풀이]
동적계획법
메모이제이션
- 재귀를 사용할 경우, 동일한 계산의 반복으로 시간 효율이 떨어진다.
- 계산한 결과를 메모리에 저장해두어 중복 계산을 방지할 수 있다.
[구현 코드]
import sys N = int(sys.stdin.readline()) cases = list(int(sys.stdin.readline()) for _ in range(N)) fibo = [[1,0],[0,1]]+[[0,0] for _ in range (max(cases)-1)] for i in range(2,max(cases)+1): fibo[i] = [x+y for x,y in zip(fibo[i-2],fibo[i-1])] for case in cases: print(*fibo[case],sep=' ')
[실행 결과]
728x90'__Python > __Algorithm' 카테고리의 다른 글
[Python] 백준 - 1904 01타일 (0) 2021.12.21 [Python] 백준 - 9184 신나는 함수 실행 (0) 2021.12.21 [Python] 백준 - 11047 동전 0 (0) 2021.12.20 [Python] 백준 - 1874 스택 수열 (0) 2021.12.20 [python] 백준 - 1654 랜선자르기 (0) 2021.12.20