[Algorithm] 피보나치 수열

피보나치 수열이란,

1,1,2,3,5,8,13,21,34,55,89,144... 등으로

첫항과 두번째항을 더해서 세번째항이 나오고,
두번째항과 세번째항을 더해서 네번째항이 나오고,
세번째항과 네번째항을 더해서 다섯번째항이 나오고,
.
.
.

이렇게 값이 늘어가는걸 피보나치 수열이라고 한다.

하나의 항을 봤을때 식으로 정리하면

a의 n+2승은 a의 n+1승 더하기 a의 n승이 될수 있다.
a의 n+2 = (a의 n+1) + (a의 n)
n승 = (n-1) + (n-2) 라고도 할 수 있다.

코드로 구현

function solution(n) {
    let result = 1;
    let pre = 1;
    
    for(let i = 2; i < n; i++) {
        const temp = result;
        result += pre;
        pre = temp;
    }
    
    return result;
}