프로그래머스 - 피보나치 수 문제
피보나치 수는 0,1,1,2,3,5,8,13,21 ... 이런식으로 전의 수와 전전의 수를 더한 값이 계속 이어지는 수열이다. 처음에는 단순하게 재귀함수로 풀어 보았다. function solution(n) { if (n === 0) return 0; if (n === 1) return 1; return (solution(n - 1) + solution(n - 2)) % 1234567; }처음 0과 1은 그대로 리턴하고 3번째 숫자(인덱스2)부터 규칙을 적용하여 재귀로 풀었다. 하지만, 큰 수가 들어갈 때는 재귀하는 횟수가 많아 콜스택 에러, 런타임 에러가 났다. 또, 함수를 한번 호출하면 두번의 호출을 더 하기 때문에 시간 복잡도는 O(2^n)으로 매우 비효율적이다. 사진처럼 단지, 피보나치의 7번째 ..
2021. 11. 8.
