피보나치 수에 대해 알아보자

피보나치 수는 

0번째 항과 1번째 항을 더하면 2번째 항의 값이라는 말이다.

간단히 쓰면 F3 = F2 + F1이다.

 

이 피보나치 수는 경우의 수를 따질 때 유용하게 쓰인다.

피보나치 수열의 n번째 항을 구하는 알고리즘은 아래와 같다.

 

function Fibonacci(n) {
if(n <=1) return n
let result = 0;
let numA = 0;
let numB = 1;

	for(let i = 2 ; i <=n ; i++) {
    	result = numA + numB;
        numA = numB;
        numB = result;
    }
    return result
}

n번째 피보나치 수열에서 n이 1보다 작거나 같으면 n을 바로 리턴한다.

 

그리고 n번째 숫자를 찾기 위해 result에서 두 피보나치 수 numA와 B를 더한다.

numA에 다음 피보나치 수인 numB를 할당한다.

이후 numB에 result를 할당한다.

 

n개의 갯수를 구하거나 1,1,2,3,5,8...같은 배열이 반복되면

피보나치 수임을 깨닫고 문제에 접근해보자!