vip1408   1년 전

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

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

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

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

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

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

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

.......

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

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

kesakiyo   1년 전

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

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