[프로그래머스 😈] JavaScript 피보나치 수

😈 피보나치 수

 

📗 문제 설명

피보나치 수는 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은 2 이상 100,000 이하인 자연수입니다.

---

📃 입출력 예

n	return
3	2
5	5

 

---

💬입출력 예 설명

입출력 예 설명 #1

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

---

💎나의 풀이

우선 피보나치 수열이 무엇인지, 그리고 알고리즘을 따져보자

출처 : 나무위키

뜻을 풀어보자면 기준이 되는 항 이전에 있는 두개의 항의 합이 기준이 되는 항 이다.

복잡하니 식으로 따져보자

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

조금만 항을 나열해보면 1, 1, 2, 3, 5, 8, 13, 21 ... 이렇게 나열이 된다.

6번째 항인 8을 보면 이전에 3, 5의 합과 같다.

다른 항도 보자 13은 5,8의 합 21은 8과 13의합이다.

이 내용이 피보나치 수열이다.

여기까지만 알아보고 알고리즘을 생각해보자.

F(n) = F(n-2) + F(n-1) 식으로 함수를 짜보면

const fibonacci = n => n <= 2 ? 1 : fibonacci(n-2) + fibonacci(n-1);

1
1
2
3
5
8
13
21

아까 봤던 수열이 나온다.

이 내용으로 문제의 요구사항을 풀어보자.

const solution = n => n <= 2 ? 1 : (solution(n-2) + solution(n-1))%1234567;

테스트 1 〉	통과 (0.03ms, 33.5MB)
테스트 2 〉	통과 (0.04ms, 33.6MB)
테스트 3 〉	통과 (0.07ms, 33.4MB)
테스트 4 〉	통과 (0.07ms, 33.4MB)
테스트 5 〉	통과 (0.05ms, 33.4MB)
테스트 6 〉	통과 (0.09ms, 33.5MB)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (런타임 에러)
테스트 14 〉	실패 (런타임 에러)

테스트 케이스에서 실패한다.

이유를 알아보자.

피보나치 수열은 어느정도 항에 도달하면 상당히 높은 정수가 될 것이다.

이 재귀 알고리즘의 시간과 공간 복잡도는 모두 O(2^N)으로 매우 비효율이라 한다.

즉, 재귀 함수의 인자로 넘기는 숫자가 커지면 실행 시간이 비약적으로 증가하게 되고,

프로그램을 실행하는 컴퓨터마다 다르겠지만, 이 재귀 함수에 어느 정도의 값을 넘기면

실행 속도가 현저히 느려질 것이다.

이 재귀 알고리즘이 어떻게 호출이 되는지 확인해보자.

solution(5)
├── solution(4)
│   ├── solution(3)
│   │   ├── solution(2)
│   │   │   ├── solution(1)
│   │   │   │   ├── solution(0)
│   │   │   │   │   └── returns 0
│   │   │   │   └── returns 1
│   │   │   └── solution(1)
│   │   │       ├── solution(0)
│   │   │       │   └── returns 0
│   │   │       └── returns 1
│   │   └── returns 2
│   ├── solution(2)
│   │   ├── solution(1)
│   │   │   ├── solution(0)
│   │   │   │   └── returns 0
│   │   │   └── returns 1
│   │   └── solution(0)
│   │       └── returns 0
│   └── returns 3
└── returns 5

solution(5) 를 호출하게 되면 중복 계산이 많이 일어나는 것을 볼 수있다.

함수 호출 스택이 계속해서 쌓이면 메모리가 늘어나 위에 테스트케이스 실패와 같이

스택 오버플로우가 발생할 수 있다.

이 오버플로우를 방지하기 위해선 중복 계산을 피해야한다.

중복 계산을 피하기 위해서 반복문을 사용해서 이미 계산된 값을 배열에 저장하는 방식으로 코드를 짜보았다.

우선 피보나치 수열의 첫번쨰와 두번째 값은 각각 0,1 로 시작한다.

그렇기 때문에 배열의 초기 값을 [0,1] 로 시작하였다.

const solution = n => {
  let answer = [0,1];
  return answer
}

앞서 설명했던 F(n) = F(n-2) + F(n-1) 을 반복문에 그대로 활용하고,

answer[i] = (answer[i-2] + answer[i-1]) 계산식을 통해 2 ~ n 까지의 항을 계산해서 배열에 저장 하였다.

const solution = n => {
  let answer = [0,1];
  for(let i = 2; i<=n; i++){
    answer[i] = (answer[i-2]+answer[i-1])
  }
  return answer
}

 console.log(solution(3))
 console.log(solution(10))

// 3
[0,1,1,2]
// 10
[0,1,1,2,3,5,8,13,21,34,55]

 

이제 마지막 값인 n 값만 가져오면 된다.

하지만 2 < n < 100,000 이다.

값이 어느정도 커지면 정수가 굉장히 커질 수 있기 때문에 1234567로 나눈 나머지 값을 요구 사항으로 준 거 같다.

const solution = n => {
  let answer = [0,1];
  for(let i = 2; i<=n; i++){
    answer[i] = (answer[i-2]+answer[i-1])%1234567
  }
  return answer[n]
}

 console.log(solution(3))
 console.log(solution(10))

정상적으로 작동한다.

수학 공부는 너무 힘들다.