재귀호출, 분할점령, 동적계획법이 끝났으면 절반 끝난것이다.
#recursion
#정의에 맞게 n-1일때와 n-2일떄의 값을 더해서 출력해줌.
def fibrec(n):
if n<2:
return n
return fibrec(n-1)+fibrec(n-2)
2가지의 sub-problem을 더해서 출력한다.
단점은 시간이 엄청 오래 걸린다. n이 30만 넘어가도 1초이상 걸린다. 자기자신을 무지막지 하게 실행하기 때문이다.
물론 분할점령은 아니다. 오히려 분할해서 문제를 크게 키우는 듯한 느낌이 든다.
#top-down dynamic programing
#memoization
#위에서 반복 계산되는 부분을 저장한후 활용
memfib={}
def fibdown(n):
global memfib
if n<2:
return n
if n in memfib:
return memfib[n]
r=fibdown(n-1)+fibdown(n-2)
memfib[n]=r
return r
위에 재귀호출에서 계산한 것을 저장하는 코드를 추가함.
그러면 이미 계산한것을 다시 계산하지 않아도 되기 때문에 함수의 호출이 상당히 많이 줄어든다.
다만 n이 2900정도를 넘어가면 재귀 호출이 너무 많다는 오류가 나온다. 이럴때는 sys.setrecursionlimit()명령어를 이용해야 한다.
#bottom-up dynamic programing
#위와는 반대로 1부터 순열을 구해서 n까지 도달하게함
def fibup(n):
mem=[0]*(n+1)
mem[1]=1
for i in range(2,n+1):
mem[i]=mem[i-1]+mem[i-2]
return mem[n]
1부터 순열을 구하기 때문에 재귀호출에 대한 부담을 줄인다.
만일 top-down에서 사용한 방법이 1부터 n까지 중에서 일부만 구해서 답을 내는 경우라면 이 방법이 메모리를 더 차지 할 수도있다. 여기서는 1부터 n까지 모든 메모리를 미리 할당하기 때문이다.
n이 50000정도면 1초안에 돌아간다.
배열에는 다음과 같이 들어간다.
| 0 | 1 | 2 | 3 | 4 | 5 | … | n |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 2 | 3 | 5 | … | fib(n) |
#bottom-up dynamic programing + 슬라이딩
#첨조할 필요가 없는 부분은 기억하지 않음.
def fibupsl(n):
i=0
j=1
for _ in range(1,n+1):
i=i+j
j=i-j
return i
루프문 하고 변수 2개만 돌아가서 간단해 보인다.
그래도 개념상으로는 마찬가지로 동적계획법이다.
위의 동적계획법 2에서 루프가 1부터 n까지 돌아가지만 참조하는 변수는 n-1과 n-2이렇게 2가지 밖에 없다. 그래서 변수 2개만 기억하고 있어도 계산이 된다.
과정은 이와 같이 진행이 된다. 그리고 i와 j의 값이 바뀔때마다 i의 값이 피보나치 수열의 수가 된다. 즉 i의 값이 fib(n)라면 j는 fib(n-1)인 셈이다. n이 하나 증가하면 자연스럽게 i=fib(n-1), j=fib(n-2)이기 때문에 둘을 더한값이 fib(n)이 됨. 이런 과정으로 이어진다.
| n | i | j | fib(n) |
|---|---|---|---|
| 0 | 0 | 1 | |
| 1 | 0+1=1 | 1 | |
| 1 | 1 | 1-1=0 | fib(1)=1 |
| 2 | 1+0=1 | 0 | |
| 2 | 1 | 1-0=1 | fib(2)=1 |
| 3 | 1+1=2 | 1 | |
| 3 | 2 | 2-1=1 | fib(3)=2 |
| 4 | 2+1=3 | 1 | |
| 4 | 3 | 3-1=2 | fib(4)=4 |
| 5 | 3+2=5 | 2 | |
| 5 | 5 | 5-2=3 | fib(5)=5 |
| … | … | … | … |
| n | i+j=fib(n) | fib(n-2) | fib(n) |
| n | fib(n) | i-j=fib(n-1) | fib(n) |
장점은 메모리를 덜 잡아먹음.
걸리는 시간은 위랑 비슷하다. 루프가 n번 돌아가는건 마찬가지다.
#행렬의 거듭제곱
def fibmat(n):
aa=[[1,1]
,[1,0]]
def mm(a,b):
r=[[0,0],[0,0]]
r[0][0]=(a[0][0]*b[0][0])+(a[0][1]*b[1][0])
r[0][1]=(a[0][0]*b[0][1])+(a[0][1]*b[1][1])
r[1][0]=(a[1][0]*b[0][0])+(a[1][1]*b[1][0])
r[1][1]=(a[1][0]*b[0][1])+(a[1][1]*b[1][1])
return r
t=aa
for _ in range(1,n):
t=mm(t,aa)
return t[1][0]
함수 mm()은 2개의 2x2행렬을 곱한 행렬을 리턴.
행렬로 피보나치를 어떻게 구하는지 조금더 보자.
행렬 aa의 초기값은 다음과 같다.
| fib(2) | fib(1) |
|---|---|
| fib(1) | fib(0) |
값으로 표현하면
| 1 | 1 |
|---|---|
| 1 | 0 |
가된다.
aa를 곱해주면
| 2 | 1 |
|---|---|
| 1 | 1 |
이다.
다시 aa를 곱하면
| 3 | 2 |
|---|---|
| 2 | 1 |
가된다.
처음에 aa의 1승이기 때문에 fib(1)은 이미 들어가있다. 그래서 n-1번 반복해 곱하면 다음과 같은 값이 행렬에 들어가 있게 된다.
| fib(n+1) | fib(n) |
|---|---|
| fib(n) | fib(n-1) |
우리가 원하는 숫자는 오른쪽 하단에 있다.
이렇게 이전항 2개를 더하는 문제를 n번 거듭제곱하는 문제로 풀 수 있다. 루프는 마찬가지로 n번 돌아가지만 행렬을 곱하는 시간이 있어서 조금 더 걸린다. 하지만 이 방법의 진가는 바로 밑에 나옴.
#행렬의 거듭제곱 + 거듭제곱을 분할점령 : 지수연선을 최적화
def fibmatoptpow(n):
aa=[[1,1]
,[1,0]]
def mm(a,b):
r=[[0,0],[0,0]]
r[0][0]=(a[0][0]*b[0][0])+(a[0][1]*b[1][0])
r[0][1]=(a[0][0]*b[0][1])+(a[0][1]*b[1][1])
r[1][0]=(a[1][0]*b[0][0])+(a[1][1]*b[1][0])
r[1][1]=(a[1][0]*b[0][1])+(a[1][1]*b[1][1])
return r
def mmpow(a,n):
if n==1:
return a
if n%2==0:
t=mmpow(a,int( n/2 ) )
return mm(t,t)
t=mmpow(a,n-1)
return mm(t, a )
t=mmpow(aa,n)
return t[1][0]
분할점령으로 거듭제곱을 하기 때문에 n번 반복하는 것이 아닌 log2(n)반복하기 때문에 엄청 빨라진다. n이 200이라면 행렬의 곱셈을 9번해서 fib(200)의 값을 구한다. n이 2000이면 16번.
mmpow()는 분할점령을 이용하여 행렬 a를 n번 거듭제곱해서 리턴한다.
이제 책에 나머지 절반에는 기하, 자료구조등이 남았을 것이다.
#de moivre: 수열의 일반항을 계산함
#실수연산과 거듭제곱연산이 들어감.
def fibmoi(n):
sqrt5=5**(1/2)
r1=(1+sqrt5)/2
r2=(1-sqrt5)/2
return (1/sqrt5)*(r1**n-r2**n)
황금비를 사용해서 구함. 그런데 무려 실수연산을 하고 거듭제곱을 한다. 실수형을 리턴하지만 필요한 답은 정수임으로 넘어감.
def fibmath(n):
if n<2:
return n
if n==2:
return 1
k=n//2
return fibmath(k+1)*fibmath(n-k)+fibmath(k)*fibmath(n-k-1)
수학적인 방법을 이용해서 호출되는 수를 줄임. n이 40일때 그 다음에는 절반정도인 20이 호출되는 식으로 건너뛰고 절반으로 바로 가기때문에 호출하는 수가 줄어든다.
당연히 여기에 memorization을 적용해도 된다.
참고
동적 계획법에 대해서 처음 배울때는 막연히 bottom-up방식 동적계획법만 배워서 어렵게 생각했었다. 하지만 recursion에 단순히 memorization를 추가하는 것만으로 top-down 동적계획법이 되는것을 알았다. 그리고 이전에 어렵게 생각했던 bottom-up방식에 대해 보고 있다.
그러면서 여려가지 방식으로 피보나치 수열을 구하는 문제들을 보고나서 한번 정리를 해보았다. 피보나치 하나로 이렇게 우려먹을수 있다는걸 보았기 때문이다.