글 읽기 - (파이썬) 2가지 코드의 차이를 잘 모르겠습니다...(피보나치 수열)

osh1795 2년 전 0

제가 피보나치 수열을 구하는 코드를 짜봤는데 리스트의 위치에 따라 계산량의 차이가 확연히 차이가 나더라구요.

#1은 리스트 생성을 함수 안에서 해주었고 #2는 리스트 밖에서 해줬습니다.

혹시 계산량의 차이가 나는 이유를 알 수 있을까요???

#공통부분
num=int(input())

#1 - 리스트가 함수 안에서 생성된 경우 (계산량이 많음)

def f(n):               #피보나치 함수 생성
    case=[-1 for k in range(num+1)] #함수에 사용될 case 생성해주기(값이 아직 안구해졌으면 -1을 가짐)
    if case[n]!=-1:  #-1의 값을 가진다면 아직 값이 안들어간 상태 >> -1이 아니라면 값이 들어간 상태
        return case[n]
    elif n==0:      #fib(0)=0
        case[n]=0
        return case[n]
    elif n==1:      #fib(1)=1
        case[n]=1
        return case[n]
    else:
        case[n]=f(n-1)+f(n-2) 
        return(case[n])

print(f(num)) #출력

#2 - 리스트가 함수 밖에서 생성된 경우 (계산량이 적음)

def fib(case,n):               #피보나치 함수 생성
    if case[n]!=-1:  #-1의 값을 가진다면 아직 값이 안들어간 상태 >> -1이 아니라면 값이 들어간 상태
        return case[n]
    elif n==0:      #fib(0)=0
        case[n]=0
        return case[n]
    elif n==1:      #fib(1)=1
        case[n]=1
        return case[n]
    else:
        case[n]=fib(case,n-1)+fib(case,n-2)
        return(case[n])

case=[-1 for k in range(num+1)] #함수에 사용될 case 생성해주기 - 값이 안들어가면 -1
print(fib(case,num)) #출력

dbshin59 2년 전 0

1번 코드는 배열을 공유하지 않습니다.

함수가 호출될 때마다 항상 배열을 새로 만들기 때문에 항상 계산이 되지 않은 상태를 나타내는 -1을 가지게 됩니다.

그러나, 2번 코드는 배열을 모든 함수가 공유하기 때문에 계산량이 줄어듭니다.

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

문제

문제

출처

ICPC

(파이썬) 2가지 코드의 차이를 잘 모르겠습니다...(피보나치 수열)

osh1795 2년 전 0

dbshin59 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말