실패한 풀이
#실패한 나의 풀이
def solution(n):
if n==1 or n==2:
return 1
elif n>2:
return (solution(n-1)+solution(n-2))%1234567
▶ 시간복잡도 O(2^n)
성공한 풀이- for문, 재사용 O
def solution(n):
if n==1 or n==2:
return 1
result =[0]*(n+1)
result[1]=1
result[2]=2
for i in range(3, n+1):
result[i]=result[i-1]+result[i-2]
return result[n]%1234567
▶ for문을 써서 재귀함수의 호출을 방지하고, 배열을 사용하여 구한 값의 재사용성을 높인다.
▶ 시간복잡도 O(n)
'프로그래머스(파이썬) > LV.2(파이썬)' 카테고리의 다른 글
행렬의 곱셈★★★→3중 for문 (0) | 2022.12.26 |
---|---|
1차 캐시→체크리스트X, OrderedDict()★★ (0) | 2022.12.26 |
예상 대진표 ★★ (0) | 2022.12.25 |
점프와 순간 이동→재귀함수(DFS)★★ + 동적 계획법 (0) | 2022.12.25 |
N개의 최소공배수→연쇄법칙★ + if not stack: 스택이 비어있다면 (0) | 2022.12.24 |