재귀 함수를 이용해 구하기
def fibo(n):
if n<2: return n
return fibo(n-1) + fibo(n-2)DP방식
def fibo(n):
if dp[n] == -1:
dp[n] = fibo(n-1) + fibo(n-2)
return dp[n]
n = 7
dp = [-1]*100
dp[0] = 0
dp[1] = 1
print(fibo(n))배열과 반복문
n = 7
dp = [0]*100
dp[1] = 1
for i in range(2,n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])재귀 함수 설명
피보나치를 재 귀하며 구하는 코드는 아래와 같다.
def fibo(n):
return fibo(n-1) + fibo(n-2)
재귀함수는 그림으로 본다면 피라미드 처럼 점점 넓어지며 내려가게 된다.
n의 값이 점점 작아지게 된다.
여기서, 재귀를 어느 값에 도달하게되면, 계산을 그만두게 해야한다.
def fibo(n):
if n<2: return n
return fibo(n-1) + fibo(n-2)피보나치의 수열에서는, 0과 1은 지정된 값이므로
조건문을 이용하여 n의 값이 0과 1에 도달될때는
재귀를 멈추고 값을 반환하는 작업을 한다.
그림으로 본다면 다음과 같다.
계산을 이어나가고.
값을 반환하고
최종적으로 구해진 결괏값을 반환하게된다.
문제는, 피라미드 형태로 값을 계산하며 써 내려가다보니.
아래의 그림과 같이 반복된 값을 또 계산해야 하는 경우가 생긴다.
dp를 이용한 풀이 설명
재귀함수를 사용한 풀이방법의 단점은
이미 계산했던 작업을 또 하고 또하고 또 반복하는 바람에 연산속도가 느려진다는 점 이였다.
dp는 계산한 내용들을 리스트에 담아두고,
반복된 계산을 할때 이미 계산한 값은, 다시 계산하지 않는 방법이다.
def fibo(n):
if dp[n] == -1:
dp[n] = fibo(n-1) + fibo(n-2)
return dp[n]
n = 7
dp = [-1]*100
dp[0] = 0
dp[1] = 1
print(fibo(n))dp = [-1]*100
피보나치의 수는 음수인 경우가 없으므로,
-1의 값으로 모두 초기화 하여,
계산한적 없는 수를 -1로 판단하도록한다.
먼저, 좌항만 쭉 내려가 계산하고 돌아올때, 다시 우항을 갔을때
" 5번 인덱스는 이미 좌항에서 계산 한적이 있으니 넘어가자 ~ "
이런 방법으로 리스트에 기록된 값을 참조해서
계산한 적 있던 것을 리스트에 기록해 기억하는 방법이다.
배열을 이용한 풀이 방법
n = 7
dp = [0]*100
dp[1] = 1
for i in range(2,n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])n = n-1 + n -2
0+1 = 1
1+1 = 2
1+2 = 3
2+3 = 5
3+5 = 8
5+8 = 13
피보나치의 수의 계산 방식을 직관적으로 그대로 적어내려간것이다.
개인적으로 가장 직관적이고 쉬우면서도, 또 가장 빠르다.
직관적이고, 쉽고, 빠르고.. 가장 좋은 구현 방식 아닐까?
