글 읽기 - 시간초과라고 뜨는데요

ssleap 7년 전 0

재귀함수를 너무 많이 쓴건가요?

T = int(input())

def fibo(n):
	if n==0:
		
		return 1
	elif n == 1:
		
		return 0
	else:
		
		return fibo(n-1)+fibo(n-2)
def fibo1(n):
	if n==0:
		
		return 0
	elif n == 1:
		
		return 1
	else:
		
		return fibo1(n-1)+fibo1(n-2)
for i in range(T):
	N = int(input())
	print(fibo(N),fibo1(N))

yclock 7년 전 2

네. 그런 것 같습니다.

어떤 정수 X가 고정되어 있을 때, fibo(X)의 값이 항상 일정함을 이용해서, 최적화를 할 수 있습니다.

1207koo 7년 전 2

위의 분이 설명하시기는 했는데 추가 설명 하자면 함수 호출 수가 거의 fibo(n)만큼 됩니다(결국 fibo(1)정도 까지 내려가야 값이 나오는데 이는 1이므로 거의 같은 횟수)

즉 시간이 지수함수처럼 증가할 수 밖에 없습니다.

만약 fibo(x)를 이미 계산했다면 그 값을 저장해놓고, 저장하는 곳에 값이 있으면 fibo(x-1)+fibo(x-2)대신 그 값을 불러오면 빨라집니다

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

문제

문제

출처

ICPC

시간초과라고 뜨는데요

ssleap 7년 전 0

yclock 7년 전 2

1207koo 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말