(자바스크립트 알고리즘) 피보나치 수 - kimyang-sun

자바스크립트 알고리즘 (Programmers)

---

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

 

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 조건

• n은 1이상, 100000이하인 자연수입니다.

 

입출력 예

---

문제 풀이

function solution(n) {
    let numbers = [0, 1];
    for(let i = 2; i <= n; i++) {
        numbers.push((numbers[i - 1] + numbers[i - 2]) % 1234567);
    }
    return numbers[n];
}

풀이입니다.

 

피보나치 수의 예시는 토끼가 1월에 한쌍이 있고, 성인 토끼로 자라는데 한달이 필요하고,

한달에 한쌍 토끼를 낳고, 절대로 죽지 않는다고 가정하고 계속 반복하는데 이때 토끼 전체의 수가 피보나치 수이고,

총합, 0,1,1,2,3,5,8,13,21,34,55,89,144,233,⋯ 순열을 피보나치 순열이라고 부릅니다.

 

여기서 n에 특정수가 들어가고 n번째 피보나치 수를 구하면 되는 문제입니다.

 

피보나치 수는 for문을 사용해도 되고 재귀함수로도 풀 수 있는데,

 

재귀함수일 경우에는 n의 값이 높아졌을때 응답이 느려지는 문제점이 보이기도 했습니다. (다른 사람들의 풀이)

 

numbers라는 피보나치의 순열이 될 배열을 만들어 우선 [0, 1]을 넣어줍니다.

0은 0번째 피보나치 수 1은 1번째 피보나치 수입니다.

 

for 반복문으로 2부터 n까지 반복을 해주는데,

numbers[i - 1] 즉 현재 배열의 마지막 숫자에서 numbers[i - 2] 마지막에서 두번째 숫자를 더해준 값을

numbers에 push 해주면 됩니다.

(% 1234567로 나눈 나머지를 리턴하라고 했으니 % 1234567을 추가로 해줍니다)

 

그리고 numbers 에 n번째 숫자를 리턴해줍니다.

 

설명을 더하자면 미성년 토끼가 1월에 한 마리가 있고, 2월에는 그 토끼가 성년으로 됐지만 자식을 낳지는 못하기에

1이 그대로입니다. 3월에는 성년 토끼가 한 마리의 자식을 낳으니까 총 2마리가 되고 이것이 반복되는 겁니다.

 

수치로 이해하는 피보나치 수 (출처 Software Carpentry) 

다른 사람들의 풀이

function fibonacci(num) {
  if(num < 2) return num;
  
  return fibonacci(num-1) + fibonacci(num-2);
}