점화식1 [python] 1003. 피보나치 함수 문제 출처 1003. 피보나치 함수 풀이 피보나치를 재귀로 짰을때 0과 1이 리턴되는 횟수를 구하는 문제이다. 이 문제를 처음에는 재귀로 풀었는데 시간 복잡도 O(2^N)으로 시간 초과가 났다. 시간을 줄이기 위해 재귀가 아닌 for문을 이용해 이 전에 계산한 결과를 저장해 다음 결과를 도출하는 DP로 풀었더니 시간복잡도가 O(N)이 나왔다. 재귀 코드(시간초과) def fib(n): global zero, one if n == 0: zero += 1 return 0 elif n == 1: one += 1 return 1 else: return fib(n-1) + fib(n-2) tc = int(input()) for _ in range(tc): n = int(input()) zero, one = 0, .. 2019. 6. 30. 이전 1 다음
