[혼공파] 함수의 활용 + (추가)

지난번 함수의 활용에서 재귀함수를 통해 피보나치 수를 구하는 함수를 썼었다. 

 

중간에 사실 global필터가 잘 이해가 안가고 딕셔너리 개념을 이해하기 위해서, 

 

우리 회사의 실버맨님 찾아가서 이것저것 물어보고 다시 설명을 들었다... 크 역시 우리 실버맨님..

 

지난번 코드를 보시면,,,

dictionary = {
    1: 1,
    2: 1
}


#함수를 선언 
def fibonacci(n):
    if n in dictionary:
        #메모가 되어있으면 메모된 값 출력
        return dictionary[n]
    else:
        #메모가 안된거면 값을 구한다 
        output = fibonacci(n-1) + fibonacci(n-2)
        dictionary[n] = output
        return output
    
#함수를 호출 
print("fibonacci(10):", fibonacci(10))
print("fibonacci(20):", fibonacci(20))
print("fibonacci(30):", fibonacci(30))
print("fibonacci(40):", fibonacci(40))
print("fibonacci(50):", fibonacci(50))

딕셔너리를 먼저 호출해주고 약간 탑다운 형식?으로 쭉 하나하나 계산해주는 것이였다. 

 

 

실버맨의 도움으로  더 간단하게 코드를 수정하자면,

def fib(n):
    if n==1 or n==2:
        return 1
    
    nums = [0] * (n+1) # nums[0, 1 ... n]
    nums[1] = 1
    nums[2] = 1

    for i in range(3, n+1): # i = 3 ... n
        nums[i] = nums[i-2] + nums[i-1]
    return nums[n]

피보나치 함수에서, f(1), f(2) 는 1이라는게 정해졌고, 

 

이제 그 뒤의 수 부터 하나씩 계산해주면 된다. 차근차근. 

 

range(3, n+1)은 3이상 n+1미만의 기간에서 하나씩 더해주는 방식. 

 

위는 탑다운 형식, 아래는 bottom-up형식이라 더 빠르다고 하셨다. 

 

하나씩 연산하는 노드의 값을 쭉 다 계산하는 것 보다 훨 빨랐다. 

 

전혀 버벅거림이 없는 코드였다. 

 

나중에 또 다시 복습한다..!!