간단한 자바스크립트 코딩 테스트 - 피보나치 수열(Fibonacci sequence)

피보나치 수열( Fibonacci sequence)

:  첫번째는 0, 두번째는 1로 시작하며 세번째는 바로 앞의 두 수를 더한 값으로 누적해서 계산하는 규칙의 수열로
 Fn = Fn-1 + Fn-2 라는 수식으로 표현할 수 있습니다.

예)

첫 번째 숫자: 0
두 번째 숫자: 1
세 번째 숫자: 0 + 1 = 1
네 번째 숫자: 1 + 1 = 2
다섯 번째 숫자: 1 + 2 = 3
여섯 번째 숫자: 2 + 3 = 5
일곱 번째 숫자: 3 + 5 = 8

# 활용분야

1. 재귀 및 동적 프로그래밍
2. 웹페이지의 그리드 레이아웃 디자인
3. 애니메이션 효과
4. 패턴 감지 및 데이터 증가 추세 분석
5. 게임 레벨 점수나 난이도 등
6. 데이터 캐싱 전력 및 로드 밸런싱

# 피보나치 수열 계산 코드

1) 일반적인 방식

function fibonacci(n) {
    var answer = 0;

    if (n <= 2) {
        answer = n;
    } else {
        let a = 0, b = 1;
        for(let i = 2; i <= n; i++) {
            let temp = a + b;
            a = b;
            b = temp;
        }
        answer = b;
    }

    return answer;
}

2) 재귀 방식

function fibonacci(n) {
    var answer = 0;

     if(n >= 2) {
         answer = fibonacci(n - 1) + fibonacci(n - 2);
     } else {
         answer = n;
     }

    return answer;
}

3) 성능 개선 방식

function fibonacci(n) {
    var answer = 0;
    var F = [0, 1]; // 초기 값으로 0, 1로 설정합니다.
    for (let i = 2; i <= n; i++) { // for 반복문을 사용하여 n번 반복합니다.
        F[i] = (F[i-1] + F[i-2]) % 1234567; // 매 반복마다 F[i]의 값을 갱신 하고 1234567로 나누어 오버플로 방지합니다.
    }
    answer = F[n]; // n번 반복 후 a가 n번째 피보나치 수가 됩니다.

    return answer;
}