kikikizoa   1년 전

시간 초과가 계속 나오는데... 제귀함수가 그렇게 오래걸리는 걸까요 ㅠㅠ

kesakiyo   1년 전

일단 시간초과의 이유부터 설명하기 전에 알고리즘의 시간복잡도를 계산하는것이 먼저일것 같네요.

피보나치 함수 내에서 재귀호출이 몇번 일어나고 그게 몇번 반복이 될까요?

대략적으로 계산해 본다면 O(2^n) 이라는 수치가 나오게 됩니다.

만약 n이 40이라면 계산량은 2^40 이 되어 꽤나 큰 수가 나오게 됩니다.

이렇기 때문에 단순 재귀호출이 아닌 좀 다른 알고리즘을 필요로 하게 됩니다.

예를 들자면 다이나믹 프로그래밍을 이용해 O(2^n) 을 O(n)으로 줄이는 방법이 있겠네요.

<사실 이 문제 인풋이 살짝 빈약해서 최적화된 재귀호출을 짠다면 1980ms에 통과를 하는 비밀이....>

movie_jo   1년 전

!!!!!!!!!!!!!!!!!!!!!!

여기 예시가 잘 나와있네요... 만능링크!

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