ijm91   8년 전

재귀여서 오류인건 알겠는데 어찌 고쳐야할지를 잘모르겠네요...

당연히 memoization 쓰면 호출을 안하니까 0 1이 고정돼서 나오니까 틀린건데..

어떤식으로 시간을 줄여야하는지 궁금합니다..ㅠㅠ

gallopsys   8년 전

재귀로 구현한 피보나치 함수에 숫자를 대입시켜보시고, 어떻게 값이 나오는지 확인하신다면 이 문제를 해결하는 실마리를 얻으실 수 있을 거예요.

ijm91   8년 전

값은 제대로 나오는거 같습니다.. 혹시 문제있는부분이 있나요?? 시간 단축을 어떻게 시켜야하는지 감이안오네요..

ijm91   8년 전

분기 if를 else if 를 주고, else 를 줬더니 맞았습니다가 떳네요..와..ㅠㅠ

혹시 이게 시간차이가 얼마나 나는지 알수있는 방법도 있나요??

gallopsys   8년 전

재귀 함수를 쓰지 않고 좀 더 빠르게 이 문제를 해결할 수 있는 방법도 존재합니다. 한 번, 방금 제출해서 맞으신 코드로 아래 내용이 맞는지 테스트 해보시길 바랍니다.


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년 전


D[n] = d[n-1] + d[n-2] 네요..ㅋㅋ감사합니다..

댓글을 작성하려면 로그인해야 합니다.