Fibonacci Coding
Fibonacci numbers with matrix
피보나치 수를 행렬을 이용하여 효율적으로 계산할 수 있다.
How to prove Fibonacci sequence with matrices?
Fast power algorithm
어떤 수 a를 n번 곱한 거듭제곱을 계산할 때, 단순히 n번 곱하는 알고리즘의 수행시간은 O(n) 이지만, 이를 O(lg n) 으로 줄일 수 있다.
Pisano period
피보나치 수열을 어떤 수 m으로 나눈 나머지는 주기를 이룬다. 이 주기를 피사노 주기라고 한다. 브루트포스로 생각하면 앞에서 계산한 모든 항에 대해 비교를 해야할 것 같지만 사실은 그렇지 않다. 피보나치 수의 정의와 모듈로 연산의 성질을 이용하면 비교 횟수를 2회로 줄일 수 있다.
properties of modular arithmetic
모듈로의 성질 : 계산 과정에서 몇번이고 % 연산을 적용해도 결과는 같다. 왜 그럴까?
difference between a += b; AND a = a + b; in C++
: 수 타입에서는 차이가 없으나 사용자 정의 클래스에서 차이가 있다. 전자는 a를 그대로 두고 뒤에 b만 붙임. 후자는 a의 내용을 복사한 임시 객체를 생성한 뒤에 b를 더해 반환하므로 실행속도에 차이가 있다.
difference between a += b and a = a + b
sum of fibonacci numbers
n까지의 합, 짝수합, 홀수합, 제곱합 등은 아래 정리해놓은 글을 참고하자.
GCD
유클리드 호제법을 이용한 최대공약수 구하기 알고리즘.