학습 목표
피보나치 수열에 대한 이해
피보나치 수열
1) 정의
피보나치 수열이란 처음 두 항을 1과 1로 한 후, 그 다음 항부터는 바로 앞의 두 개의 항을 더해 만드는 수열을 말한다.
*문제를 살펴보면 처음 두 항은 다른 경우가 꽤 있다.
2) 동작 예시
풀이 - 1
def fibo(x):
if x==0:
return 1
elif x==1:
return 1
else:
return fibo(x-1)+fibo(x-2)
n=int(input())
print(fibo(n))
가장 기본적인 식으로, x==0과 x==1일 때 fibo(x)는 1을 처리한다.
이 외는 fibo(x-1)+fibo(x-2) 더한 값을 리턴한다.
매번 fibo(x-1), fibo(x-2) .... 계산이 계속해서 돌게 되므로, 연산이 많아지고 결과 도출이 늦어진다.
풀이 - 2
def fibo(x):
if x in dictionary:
return dictionary[x]
else:
dictionary[x]=fibo(x-1)+fibo(x-2)
return dictionary[x]
n=int(input())
dictionary={0:1, 0:1}
print(fibo(n))
dictionary type에 넣어서 각 피보나치 수열을 적고, 적어 놓은 것을 꺼내오는 방법으로 구성 해 보자.
이 경우 매번 계산을 돌릴 필요는 없고 메모된 값을 꺼내오기만 하면 된다.
if x in dictionary:
return dictionary[x] - x 값이 dictionary 내에 있는 지 확인한다. 확인하는 기준은 "key" 값이다. 예를 들어 dictionary 내용에 {0:1} 이라면 0이 해당된다.
else:
dictionary[x]=fibo(x-1)+fibo(x-2)
return dictionary[x] - dictionary 내에 없는 경우, dictionary[x]에 계산 값을 새로 적어준다. 그리고 해당 값을 리턴한다.
'파이썬 > 파이썬 기초' 카테고리의 다른 글
1의 보수, 2의 보수, Signed와 Unsigned의 모든 것 (0) | 2021.05.07 |
---|---|
파이썬 깊은복사/얕은복사 알아보기 (0) | 2021.04.26 |
[그래프] 깊이 우선 탐색 (DFS - Depth First Search) 알고리즘 (0) | 2021.02.12 |
파이썬 행렬 좌표 표현하기 - 구현 (0) | 2021.02.11 |
파이썬 각 행의 최솟값과 최댓값 구하기 (0) | 2021.02.10 |
댓글