좋은코딩

피보나치 수열

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

1. recursive를 이용한 구현

재귀호출을 이용하면 간단하게 구현할 수 있지만, n이 커질수록 연산량이 크게 증가한다. 

시간복잡도 : O(2^n) 

2. memoization을 이용한 구현

연산 결과를 저장하는 배열이 필요하지만, 재귀적 구현에 비해 월등히 빠른 속도를 낼 수 있다.

시간복잡도 : O(n) 

3. 간단한 성능 비교

* 15에 대한 피보나치 수를 구하는 실험 진행

recursive 기반 알고리즘은 180,428 cycle이 소요됨

memoization 기반 알고리즘은 6148 cycle이 소요됨

memoization 기법이 약 2900% 효율적

* CPU 성능이나 주어진 수에 따라 차이가 있을 수 있습니다.

1) 1은 소수가 아님

2) 소수인지 판단할 수 param을 2부터 param-1까지 나누어봄

    한번이라도 나머지가 0이면 param은 소수가 아님 

greatest common divisor algorithm in C

>> (u, v)

1) u가 v보다 크면 v와 u를 바꾼다. (음수 방지)

2) u = u - v

3) u == 0 이면, v가 최대공약수

   아니라면 1)로 돌아감