- 알고리즘 유형 : DP(다이내믹 프로그래밍)
- 풀이 참고 : 여러 블로그
- 문제 링크 : https://www.acmicpc.net/problem/2748
늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다.
그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사드리겠습니다.
DP 개념 정리
개념 정리 : https://kyyu.tistory.com/32
풀이 요약
처음은 재귀로 풀었다. > 시간 초과
n = int(input())
# 재귀 시간초과
count1 = 0
cc = 0
def fibonacci(x):
if x < 3:
return 1
return fibonacci(x-1) + fibonacci(x-2)
for i in range(1,n+1):
a = fibonacci(i)
print(a)
코드(python)
n = int(input())
# 답1(이게 아주 쪼금 더 빠름)
fibonacci = []
num = 0
for i in range(n+1):
if i == 0:
num = 0
elif i <= 2:
num = 1
else:
num = fibonacci[-1] + fibonacci[-2]
fibonacci.append(num)
print(fibonacci[-1])
배운 점, 배울 점
DP에 대해 이론 공부도 중요하지만 여러 문제에서 어떻게 활용되는지를 공부해야겠다.
문제를 접하며 적용되는 알고리즘을 중점으로 공부해보자
반응형
'Develop > Python' 카테고리의 다른 글
[알고리즘]백준_먹을 것인가 먹힐 것인가_7795_python (0) | 2022.12.18 |
---|---|
[Python]Asterisk(*) (0) | 2022.10.05 |
[Python]map 함수에 대해서 정리 (0) | 2022.10.04 |