반응형
https://www.acmicpc.net/problem/2748
2748번: 피보나치 수 2
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
코딩에 조금이라도 관심이 있으신 분이라면 피보나치 수열은 반드시 들어봤을 것이다.
F(n) = F(n-1) + F(n-2) 라는 식을 가진 피보나치 수열은 보통 회귀 방법으로 풀고는 한다.
하지만 이 문제도 회귀 방법으로 풀게 된다면 답은 나오지만 시간 초과가 될 것이다.
지금부터 재귀함수를 사용하지 않고 리스트를 사용하면서 피보나치 수열을 푸는 방법을 알려주겠다!
|
1
2
3
4
5
6
7
8
9
|
def fibonacci(end):
for i in range(end+1):
if i == 0:
num = 0
elif i == 1 or i == 2:
num = 1
else:
num = fibo[-1] + fibo[-2]
fibo.append(num)
|
cs |
내가 리스트로 구현한 피보나치수열 함수다.
재귀함수를 사용하지 않고 반복문을 사용해서 계산하는 방법으로 풀었다.
원래 재귀함수 방법으로 풀면
|
1
2
|
def fnc_s (n) :
return fnc_s(n-2) + fnc_s(n-1)
|
cs |
이러한 방법으로 해서 피보나치 함수를 다시 불러오는 방법으로 풀지만 리스트로 하면 반복문을 사용하기 때문에 그럴 필요가 없다.
정답 코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
fibo = []
def fibonacci(end):
for i in range(end+1):
if i == 0:
num = 0
elif i == 1 or i == 2:
num = 1
else:
num = fibo[-1] + fibo[-2]
fibo.append(num)
num1 = int(input())
fibonacci(num1)
print(fibo[-1])
|
cs |
반응형
