피보나치 수
by Cori문제
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
· F(2) = F(0) + F(1) = 0 + 1 = 1
· F(3) = F(1) + F(2) = 1 + 1 = 2
· F(4) = F(2) + F(3) = 1 + 2 = 3
· F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
제한사항
· n은 1이상, 1000000이하인 자연수입니다.
입출력 예
n | return |
3 | 2 |
5 | 5 |
풀이
1. Me
1) 1차 시도
def fibonacci(n):
return fibonacci(n-2) + fibonacci(n-1)
def solution(n):
if n == 1:
return 1
elif n == 2:
return 1
else:
return (fibonacci(n) % 1234567)
흔한 피보나치 수열 공식을 이용하여 풀었으나, 역시 효율성 테스트에서 통과하지 못했다..
2) 2차 시도
def solution(n):
df = [0] * 100002
df[0] = 0; df[1] = 1
for i in range(2, n+2):
df[i] = df[i-1] + df[i-2]
return (df[n] % 1234567)
다이나믹 프로그래밍 방법으로 풀었다. 재밌당
2. Others
def fibonacci(num):
a,b = 0,1
for i in range(num):
a,b = b,a+b
return a
대박 .. 튜플의 성질을 이용하여 간단하게 풀어내셨다.
'CS > Coding Test' 카테고리의 다른 글
최솟값 만들기 (0) | 2021.09.02 |
---|---|
콜라츠 추측 (0) | 2021.09.01 |
최댓값과 최솟값 (0) | 2021.08.31 |
JadenCase 문자열 만들기 (0) | 2021.08.31 |
N개의 최소공배수 (0) | 2021.08.30 |
블로그의 정보
코딩하는 오리
Cori