🔨 오늘의 문제 : 피보나치 수
📝 문제 설명은 여기서 확인 가능하다.
✅ 코드 실행 - 2개 중 2개 통과! (๑˙ᴗ˙๑)
❌ 제출 후 채점하기 - 14개 중 6개 통과.. ( ᴗ_ᴗ̩̩ )
➡️ 실패 전부가 시간초과 또는 런타임에러
"피보나치 수"
피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.
출처 : 위키백과
다시 말해
0 / 1 / 1 / 2 / 3 / 5 / 8 / 13 / 21 / 34 / 55 ...
첫번째와 두번째 자리는 0과 1로 고정이고, 세번째 자리부터 본인 앞 2개의 숫자를 합한 값이 된다.
💬 생각한 수도코드
- 피보나치 수열의 5번째 자리 숫자는, [3번째 자리 숫자 + 4번째 자리 숫자]로 이루어져 있다.
- 즉, fibonaci(5) = fibonaci(3) + fibonaci(4)
➡️ fibonaci(5) = fibonaci(5 - 2) + fibonaci( 5 - 1) - 결국 위 로직을 반복하다보면 fibonaci(1) 또는 fibonaci(0)을 마주하게 되는데, 피보나치 수열의 첫번째 자리 숫자와 두번째 자리 숫자는 0과 1로 고정되어있다.
- 이걸 재귀함수를 만들어 풀고, 리턴된 값을 1234567로 나눈 나머지를 리턴한다.
👩💻 코드
function solution(n) {
// 재귀함수 작성
const fibonaci = (n) => {
// base case
if(n <= 1){
return n;
}
// recursive case
return fibonaci(n - 1) + fibonaci(n - 2);
};
const result = (fibonaci(n) % 1234567);
return result;
}❗️ 체크할 점
시간 초과 또는 런타임 에러가 난 것을 보아하니 시간복잡도의 문제가 있는 거 같다. 시간복잡도와 관련해서 찾아보던 중 아주 설명이 잘 나와있는 유튜브를 찾게돼서 첨부한다.
1분 13초대
매번 함수가 호출될 때마다 2개씩 호출이 증가하고 그걸 트리의 높이만큼 반복하는데, 트리의 높이는 n보다 작은 값을 가지기 때문에, 2개씩 n번 늘어나는 알고리즘이니까 빅오표기법으로는 O(2^n)이다.
내가 작성한 알고리즘도 동영상에 나와있듯이 불필요한 작업을 많이 반복한다. 따라서 이걸 최적화하는 작업을 해야하는데, 메모이제이션(Memoization) 기법(하위 문제에 대한 정답을 계산했는지 확인해가며 하향식으로 문제를 자연스럽게 풀어나가는 방식)을 활용하면 된다.
๑•‿•๑