Fast Fibonacci Transform
큰 N에 대해서 N번째 피보나치 수를 구하기 피보나치 수열의 일반항을 구하는 함수에 대해서 오일러 프로젝트 관련 글에서 한 번 언급한 적이 있는데, 점화식을 그대로 정직하게 코드로 옮겨놓은 경우, 극히 작은 일부 n에 대해서만 실용성이 있을 정도로 비효율적이다. 35 정도를 넘기면 느려지기 시작하는데 40정도만 되어도 처참한 성능을 보여준다. 성능을 개선하기 위해서 메모이제이션 같은 테크닉을 사용할 수 있다. 미리 계산한 결과를 저장해두고 있다가 재계산을 피해서 반복횟수를 줄이는 방법이다. 메모이제이션 기능을 수행하는 데코레이터를 작성하여 함수 구현의 변경 없이 메모이제이션을 적용할 수 있다. 똑같은… 더 보기 »Fast Fibonacci Transform