vip1408   5년 전

흠....제가 짠소스에서 반복문으로 재귀함수를 호출하다보니, fibonacci(40)

즉 n의 수에 40이상의 수를 제가 임의로 집어넣어보니, 실행시간이 제한시간인 2초가 넘어가는걸로 봤습니다...

그렇다면 저기 있는 피보나치 함수를 제가 다르게 구현해야 하는걸까요?

제가 정말 아이디어가 안떠올라서 질문드려봅니다...ㅠ

ksmzzang2003   5년 전

예를 들면 fibo(10)를 알고 싶다고 하죠.

이때 f(3)은 f(9) 구할때도 계산하고

f(8) 구할때도 계산하고

.......

이렇게 중복계산이 많습니다.

이 중복계산을 없애면 시간이 확 줄어듭니다.

kesakiyo   5년 전

dynamic programming을 이용해서 시간복잡도를 줄일 수 있습니다.

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