재귀로 구현한 피보나치 함수에 숫자를 대입시켜보시고, 어떻게 값이 나오는지 확인하신다면 이 문제를 해결하는 실마리를 얻으실 수 있을 거예요.
1003번 - 피보나치 함수
재귀 함수를 쓰지 않고 좀 더 빠르게 이 문제를 해결할 수 있는 방법도 존재합니다. 한 번, 방금 제출해서 맞으신 코드로 아래 내용이 맞는지 테스트 해보시길 바랍니다.
n = 0이면, 결과값은 1 0입니다. n = 1이면, 결과값은 0 1입니다.
그럼 n = 2일 때는요? 결과값은 1 1이겠죠. fibonacci(1)과 fibonacci(0)를 호출하니까 그렇죠.
다시 n = 3일 때를 생각해봅시다. fibonacci(3)은 fibonacci(2)와 fibonacci(1)을 호출하고, fibonacci(2)는 다시 n = 2일 때 처럼 호출하겠죠. 그렇다면 결과값은 1과 2가 될 겁니다.
n = 4일 때, 확인해보시면 fibonacci(4) -> fibonacci(3), fibonacci(2) / fibonacci(3) -> fibonacci(2), fibonacci(1) / fibonacci(2) -> fibonacci(1), fibonacci(0)이므로 결과값은 2와 3이 나올 겁니다.
이제 한 번 결과값만 모아보도록 하죠!
n = 0 n = 1 n = 2 n = 3 n = 4 ...
1 0 0 1 1 1 1 2 2 3 ...
잘 보면 뭔가 규칙성이 보이지 않나요?
댓글을 작성하려면 로그인해야 합니다.
ijm91 8년 전
재귀여서 오류인건 알겠는데 어찌 고쳐야할지를 잘모르겠네요...
당연히 memoization 쓰면 호출을 안하니까 0 1이 고정돼서 나오니까 틀린건데..
어떤식으로 시간을 줄여야하는지 궁금합니다..ㅠㅠ