- n번째 피보나치 수 구하는 프로그램
- Game Development
- 2009/06/09 22:10
- Exponentiation by squaring, fibonacci, recursion, Ruby, 루비, 재귀호출, 피보나치, 황금비
-
 romanesco by docman   |
다음과 같은 피보나치 수열을 아실겁니다.
0, 1에서 출발하여 다음과 같은 재귀 관계를 만족하는 수들입니다.
실제 자연 현상에서도 다양하게 확인되며, 황금비와의 관련 등 여러 흥미로운 특징을 가지는 수가 되겠습니다.
n번째 피보나치 수를 구하기 위해 가장 단순하게는 다음과 같은 함수를 만들 수 있겠죠.
하지만 따져 보시면 알겠지만 중복 계산이 많으며, 실제 지수 시간이 걸립니다.
이를 선형 시간 안에 계산하려면, 여러가지 방법이 있습니다만, 가장 금방 생각해낼 수 있는 것이 중복 계산 방지를 위해 메모이제이션을 사용하는 겁니다. 계산 결과를 캐슁해 놓았다가 재활용하는 것이지요.
F(n)이 n번째 피보나치 수라 할 때, 위와 같은 행렬식이 성립합니다. 이렇게 거듭 제곱 형태로 변경하고 나면 제곱으로 지수값 구하기를 이용하여 효율적으로 계산하는 것이 가능해집니다. (루비 코드입니다; 친절한 설명은 여길 참조)
이것이 가장 빠른 피보나치 알고리즘은 아니지만 순진한 맨위의 초기 구현보다는 큰 n에 대해서 훨씬 빠르겠죠.
 Fibonachess by fdecomite |
매우 간단한 수학 문제지만 실제 프로그래밍으로의 구현에서는 생각할 것이 많은... 그래서 인터뷰 질문으로 매우 유용한 소재라고 생각합니다.
참고: 피보나치 수 프로그램
'Game Development' 카테고리의 다른 글
| 게임 프로그래머를 위한 Yammer 그룹 가입신청 받습니다. (13) | 2009/06/19 |
|---|---|
| 크라이텍 깜짝 선물 (2) | 2009/06/16 |
| n번째 피보나치 수 구하는 프로그램 (0) | 2009/06/09 |
| D&D-style map of C++ (2) | 2009/06/06 |
| Double-checked locking 이디엄의 함정 (2) | 2009/06/03 |
| Iterators Must Go! (in favor of ranges) (2) | 2009/05/15 |
Recent comment