[Programmers] 프로그래머스 2단계 : 피보나치 수

💡 문제 설명
피보나치 수는 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

 

나의 풀이

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

처음에 재귀함수를 사용하여 코드를 작성하였다 그런데 !!

function solution(n) {
	if(n <= 1) return n;
    return solution(n - 1) + solution(n - 2);
}

재귀함수 사용 시 발생하는 시간초과 & 런타임 에러!

확인해보니 재귀 호출을 하면 n이 50 이상일 때 시간 초과가 나거나 런타임 에러가 난다고 한다

런타임 에러가 나는 이유는 일부 언어는 재귀 호출을 할 수 있는 횟수가 정해져 있고 횟수를 넘어 재귀 호출을 하면 런타임 에러를 내도록 설계되어 있기 때문이다

 

그래서 for문을 사용하여 문제를 풀었다

fibonacci 변수에는 0, 1번째 피보나치 수를 배열 안에 넣어주었다

n이 1보다 작을 경우 배열 n번째 자리에 수를 return 하도록 하였고

아닐 경우에는 for문을 사용하여 n번째 피보나치 수를 배열 안에 넣어주도록 하였다

fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % 1234567

문제에서 보면 n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수 를 완성하라고 하기 때문에

해당 코드를 작성하여 fibonacci 배열에 n의 자리에 해당하는 요소를 return 하도록 하였다 🤯

 

실행 결과