😈 피보나치 수
📗 문제 설명
피보나치 수는 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))
정상적으로 작동한다.
수학 공부는 너무 힘들다.
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 😈] JavaScript 다음 큰 숫자 (0) | 2023.11.24 |
---|---|
[프로그래머스 😈] JavaScript 크기가 작은 부분 문자열 (0) | 2023.11.24 |
[프로그래머스 😈] JavaScript 약수의 개수와 덧셈 (1) | 2023.11.22 |
[프로그래머스 😈] JavaScript 이상한 문자 만들기 (1) | 2023.11.21 |
[프로그래머스 😈] JavaScript K번째수 (0) | 2023.11.21 |