1.
def fibo(n):
if n==1:
return 1
elif n==2:
return 2
else:
return fibo(n-1)+ fibo(n-2)
def solution(n):
num=fibo(n-1)
answer=num%1234567
return answer
피보나치 수열 구현하는거 재귀함수밖에 기억안나서 이렇게 써봄.
당연히 시간초과남.
2.
def fibo(n, memo={}):
if n in memo:
return memo[n]
if n == 1:
return 1
elif n == 2:
return 2
memo[n] = fibo(n - 1, memo) + fibo(n - 2, memo)
return memo[n]
def solution(n):
num=fibo(n-1)
answer=num%1234567
return answer
메모 어쩌구
또 시간초과 남.
3.
def fibo(n):
if n == 2:
return 2
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
def solution(n):
num=fibo(n-1)
answer=num%1234567
return answer
모든 알고리즘 문제는 다이나믹 프로그래밍으로 풀 수 있다했다. (아마 나동빈선생님께서 그랬는데)
4. 다른 사람 풀이
def fibonacci(num):
a, b = 0, 1
for i in range(num):
a, b = b, a+b
return a
이렇게도 되는군요.
시간 복잡도는 같지만 .. 다이나믹 프로그래밍 쓰면 .. 메모리를 너무 많이 쓰니까요
'코테 공부' 카테고리의 다른 글
| 프로그래머스 Lv.2 짝지어 제거하기 (1) | 2024.10.03 |
|---|---|
| 프로그래머스 Lv.2 N개의 최소공배수 (1) | 2024.10.03 |
| 프로그래머스 Lv.2 다음 큰 숫자 (0) | 2024.10.02 |
| 프로그래머스 Lv.2 숫자의 표현 (0) | 2024.10.02 |
| 프로그래머스 Lv.2 이진 변환 반복하기 (2) | 2024.10.02 |