피보나치 수열
일반 반복문 활용
def fibonacci(n):
a,b=1,1
if n==1 or n==2:
return 1
for i in range(1,n):
a,b=b,a+b #swap
return a
ex. 피보나치 수열의 5번째 값을 구하고자 할 때
for문 반복 횟수 | a | b |
---|---|---|
1 | 1 | 2 |
2 | 2 | 3 |
3 | 3 | 5 |
4 | 5 | 8 |
4번째 반복 할 때의 a값
즉, 5가 피보나치 수열의 5번째 값을 의미한다.
재귀 함수
def fibonacci(n)
# 피보나치 수열의 n번째 항들은 결국 1의 합들로 구성된것이라고 생각하면 쉬움
if n>=2:
fibonacci(n-2) + fibonacci(n-1)
elif n==1:
return 1
elif n==0:
return 0
피보나치 수열의 특성 그대로 코드를 구현해주면 되기 때문에 너무 쉽게 재귀함수로 구현할 수 있다.
그러나 재귀함수의 가장 큰 문제점은 효율성이 좋지 못하다는 점인데, 이미 계산되었던 값일지라도 의미 없이 다시 계산을 반복하기 때문이다.
따라서 이와 같은 문제점을 해결하기 위해서는 동적계획법(dynamic programming,DP)에서 활용되는 메모이제이션(memoization)을 사용해야한다.
핵심적인 것만 얘기하자면, DP에서는 큰 문제를 해결하기 위해 작은 문제들을 해결해나가야 하는데, 그 작은 문제들의 결과값은 변하지 않아야한다. 그리고 그 결과값이 변하지 않는 작은 문제들이 계속 반복해서 일어나게 된다.
여기서 메모이제이션은 자꾸만 반복되지만 그 결과값은 변하지 않는 작은 문제들의 결과값을 저장하는 것을 의미한다. 이미 결과값이 기록된 작은 문제의 경우, 메모이제이션을 통해 값을 불러온다면 불필요한 계산을 대폭 감소시킬 수 있다.
결국 재귀함수 또한 큰 문제를 해결하기 위해 탈출 조건을 만날 때까지 작은 문제들을 풀어나가야하는 행위이기 때문에, 그 과정 중에 결과값이 바뀌지 않는 작은 문제들이 존재할 수 있다.
결론적으로, 피보나치의 n번째 수를 구하는 함수에 메모이제이션 개념을 도입하면 다음과 같이 코드를 구현 할 수 있다.
메모이제이션(dp) + 재귀함수 활용
dic = {} #memoization을 위한 dictionary를 함수 외부에 선언
def fibonacci(n):
if n in dic:
return dic[n]
if n==0:
dic[0]=0
elif n==1:
dic[1]=1
else:
dic[n]=fibonacci(n-1)+fibonacci(n-2)
위 코드가 지저분해보인다면 n이 0과 1일 때의 값은 dictionary에 미리 넣어두어도 된다.
fib={0:0,1:1}
def fibonacci(n):
if n in fib:
return fib[n]
fib[n]=fibonacci(n-2)+fibonacci(n-1)
return fib[n] # return 까먹지 않기
n = int(input())
print(fibonacci(n)%1000000007)
재귀함수의 효율성이 많이 떨어진다면, 메모이제이션을 활용하여 효율성을 증대시켜보자.
메모이제이션 + 반복문 활용
n = int(input())
dp= [0,1,1] #여기서는 배열 선언
for i in range(3,n+1):
dp.append((dp[i-1]+dp[i-2])%1000000007)
print(dp[n])
sys.getrecursionlimit()
를 통해 확인 가능하며, 백준 서버에서는 이를 1,000으로 제한하고 있음재귀 → 반복문으로 변환 (쉽게 해결)
최대 재귀 깊이 리밋 늘리기
ex. sys.setrecursionlimit(10**6)