간단한) 피보나치 수열

피보나치 수열은 재귀식으로 너무 유명하다

f(0) = 0

f(1) = 1

f(n) = f(n-1) + f(n-2)

인데, 이걸 재귀식으로 하여 돌리면 실제론 무진장 오래 걸린다.

기본적으로 함수가 실행되면 stack으로 쭉쭉 위에 쌓이기 때문에 좀만 큰 숫자를 넣으면 동작이 안될것이다.

이럴땐 간단히 동적프로그래밍을 통해서 구현할 수 있다.

동적프로그래밍의 핵심은 기억해놓는것, 저 멀리 있는거를 나중에 가져오는게 아니니까 미리미리..

파이썬 코드로 하면 이러하다

a = 0;

b = 1;

for i in range num:

a, b = b, a+b;

return b

우리가 필요로 한건 앞에 두개의 숫자만 필요로 하니까 주구장창 두개만...사용.

동적프로그래밍 개념을 알아도 실제로 적용하는 것은 매우 힘들다. 후