-
33. 피보나치 수열(Fibonacci numbers)과 동적 계획법(dynamic programming)Python/파이썬 자료구조 알고리듬 2019. 6. 27. 09:29반응형
피보나치 수(Fibonacci numbers)의 역사는 적어도 기원전 700년경으로 거슬러 올라가며, 1202년 이탈리아의 수학자인 레오나르도 피보나치가 피보나치 수로 토끼의 개체 수 증가를 설명한 것을 계기로 피보나치라는 이름이 붙었다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55....
이전의 두 숫자를 더해서 다음 숫자를 만드는 수열입니다.
이제 문제만 읽어도 아 이건 재귀 문제구나 느낌이 오죠?
물론 재귀로만 이 문제를 풀 수 있는 것은 아닙니다만...
알고리듬은 역시 재귀. 재귀가 제 맛 아니겠습니까?재귀 1
자 이제 코딩을 해봅시다.
def fibonacci(a, b): print(a) return fibonacci(b, a+b) fibonacci(0, 1)이렇게 하면 함수 스택의 한계를 채우고 멈춥니다.
편하게 쓰기 위해 카운터를 만들어야겠네요.def fibonacci(a, b, c): print(a) if c == 0: return a return fibonacci(b, a+b, c-1) fibonacci(0, 1, 10)0 1 1 2 3 5 8 13 21 34 55다 만들고 나니 이게 아니었다는 게 떠올랐습니다.
생각의 흐름에 따라 코딩하다 보니..
좀 더 효율성이 떨어지는 코드를 작성했어야 동적 프로그래밍을 설명할 수 있는데. ㅠ,.ㅠ
효율이 떨어지는 모델을 만드려고 하니 의욕이 감소합니다. 그래도 만들어 봅시다.
재귀 2
재귀 + 함수가 2개로 나눠지도록 만듭니다.
def fibonacci(n): # print(n) # 이 프린트 문을 이용하면 얼마나 많은 계산을 하는 지 알 수 있다. if n < 2: return n else: return fibonacci(n - 1) + fibonacci(n - 2) print(fibonacci(10)) # 5535 정도 돌려주니 체감적으로도 차이가 느껴지네요. 아주 느린 알고리듬입니다.
한번 반복할 때 약 2배로 함수가 늘어나니, n번을 반복하면 '약 2의 n 제곱'개의 함수가 발생합니다.
아래 그림을 보면 반복되는 계산이 너무 많습니다.
위에 주석 처리한 부분을 실행해보면 실제 눈으로도 확인할 수 있습니다.
이런 식으로 복잡한 문제를 조각 조각 나누어 푸는 방식을 '하향식'이라고 합니다.
처음보면 신기합니다. 정의만 한 것 같은 데 풀이는 따라오는 듯한 느낌.메모이제이션
재귀로 fibo(6)을 계산하기 위해 5는 1번 4는 2번 3은 3번의 계산을 해야 합니다.
n이 커질수록 반복은 점점 많아집니다.
이 반복되는 계산을 첫 계산 시 저장한 뒤,
다음 계산에선 계산 없이 그 값을 읽어서 처리하도록 하면 좋겠죠?동적 프로그래밍의 가장 큰 특징은
큰 문제를 부분으로 나누고,
나눈 문제의 답을 기억해 두었다가 재활용한다는 데 있습니다.단순히 나누었다 합치면 분할정복과 다를 바가 없지 않습니까?
이것이 바로 동적 계획법 중 메모이제이션이라는 방법입니다.
코딩해 봅니다.
하향식 + 메모이제이션 입니다.
def fibonacci(n: int, memo: list): if n < 2: return n if memo[n] == 0: memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo) return memo[n] def fib_helper(n): return fibonacci(n, [0 for _ in range(n + 1)]) print(fib_helper(10))속도 측정을 해보겠습니다.
데코레이터를 이용해 보았습니다.from time import time_ns from functools import lru_cache def time_log(original_fn): def wrapper_fn(*args, **kwargs): start_time = time_ns() result = original_fn(*args, **kwargs) end_time = time_ns() print(f'Working Time [{original_fn.__name__}]: {end_time - start_time:,}') return result return wrapper_fn def fibonacci_dp(n: int, memo: list): if n < 2: return n if memo[n] == 0: memo[n] = fibonacci_dp(n - 1, memo) + fibonacci_dp(n - 2, memo) return memo[n] @time_log def fib_helper(n): return fibonacci_dp(n, [0 for _ in range(n + 1)]) print(fib_helper(100))제 컴에서는 결과가 이렇습니다.
Working Time [fib_helper]: 500,700 354224848179261915075functools.lru_cache()
파이썬의 functools 모듈에는 lru_cache()라는 데코레이터가 있습니다.
https://docs.python.org/ko/3/library/functools.html#functools.lru_cache파이썬 3.9부터는 cache라는 데코레이터도 생겼습니다.
https://docs.python.org/ko/3/library/functools.html#functools.cache이 데코레이터를 사용하면,
함수를 실행했을 때,
캐시된 리턴값이 있다면,
함수를 실행하지 않고,
이 리턴값를 재사용합니다.메모이제이션과 유사합니다.
LRU(least-recently-used) 알고리듬은
캐시가 가득 차면 사용한 지 오래된 값부터 지웁니다.from time import time_ns from functools import lru_cache def time_log(original_fn): def wrapper_fn(*args, **kwargs): start_time = time_ns() result = original_fn(*args, **kwargs) end_time = time_ns() print(f'Working Time [{original_fn.__name__}]: {end_time - start_time:,}') return result return wrapper_fn @lru_cache(maxsize=None) def fibonacci(n): # print(n) # 이 프린트 문을 이용하면 얼마나 많은 계산을 하는 지 알 수 있다. if n < 2: return n else: return fibonacci(n - 1) + fibonacci(n - 2) @time_log def main(): print(fibonacci(100)) # 55 if __name__ == '__main__': main()354224848179261915075 Working Time [main]: 499,400동적계획법
간단한 하위 문제를 해결하면서 좀 더 복잡한 상위 문제로 나아갑니다. (상향식)
하위 문제를 해결한 결과는 저장합니다.
전체 문제를 해결할 때까지 반복합니다.아래 코드는 상향식 동적계획법이라고 할 수 있습니다.
좀 더 상향식스럽게 코딩할 수도 있겠지만..
요약 정리하면 이 코드가 나오겠죠?def fibonacci(n): val = [0, 1] if n < 2: return val[n] else: for i in range(2, n+1): val.append(val[i-1] + val[i-2]) return val[n] print(fibonacci(10)) # 55좀 더 줄여 쓴다면...
def fibonacci(n): val = [0, 1] if n >= 2: for i in range(2, n + 1): val.append(val[i - 1] + val[i - 2]) return val[n]코드를 보면
val[0], val[1]의 값을 이용해서
val[1] + val[0]를 val[2]에 append 하고
append한 것은 다음 계산 시 이용하고 있습니다.
가장 쉬운(?) 해법: 슬라이딩 윈도(?)
가장 쉬운(?) 해법입니다.
재귀가 무슨 소용 있나 자괴감 들어...사실 이 해법을 가장 나중에 올린 이유는
이 해법이 상향식 동적 계획법에 슬라이딩 윈도 기법을 썼다고 해도
틀린 말은 아니기 때문입니다.동적 계획법에서는 정답을 재활용하기 위해 저장공간을 사용합니다.
만약 이때 공간을 재활용할 수가 있다면, 그렇게 하면 되겠죠?
이것을 슬라이딩 윈도 기법이라 합니다.카드만 돌려 막는 게 아닙니다.
아래 변수 v0, v1의 돌려막기가 보이지 않습니까?def fibonacci(n): if n < 2: return n v0, v1 = 0, 1 for _ in range(n - 1): v0, v1 = v1, v1 + v0 return v1 print(fibonacci(10))나는 RAND 코퍼레이션에서 1950년의 가을을 보냈다. 여기에서 내게 주어진 첫 과제는 다단계(multistage) 의사 결정 프로세스에 대해 적절한 용어를 명명하는 것이었다. '동적 계획법'이라는 이름이 어디에서 왔는지 궁금하지 않은가? 1950년대는 내가 수학에 대해 연구하기에는 좋지 못한 시기였다. 우리는 그 때 워싱턴에서 윌슨이라는 사람과 함께 일하고 있었다. 윌슨은 연구라는 것에 대해 굉장히 병적인 공포를 가지고 있었다. 사람들이 그 앞에서 연구에 대해 이야기를 꺼내면 그는 완전히 미치다시피 했다. 그러나 불행히도 RAND는 공군 소속의 회사였고, 윌슨은 그 공군의 간부인 국방 위원장이었다. 그래서 내가 RAND 안에 있었을 때 윌슨을 비롯한 공군들이 내가 수학에 대해 연구하는 것을 보이지 않게 막는다는 것을 알 수 있었다. 처음 올 때는 나는 위의 문제에 대해 '의사 결정 프로세스'라는 이름을 사용했지만, 여기에서 '프로세스(Process)'라는 단어를 사용하는데 여러가지 차질이 생겨버리고 만 것이다. 그래서 나는 사람들이 알지 못하게 '계획법(Programming)'이라는 단어를 붙였다. 또한 나는 이 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, '동적(Dynamic)'이다라는 개념(idea)이 전달되길 원했다. 이 단어야말로 내가 연구하는 알고리즘의 성질을 정확하게 짚어내었고, 게다가 윌슨에게도 피해를 입히지 않으며 공군도 이 단어에선 꼬투리를 잡지 못했으니 그야말로 일석이조의 효과를 누린 것이다.
리처드 벨먼 (Richard Ernest Bellman)
출처: 위키백과제너레이터
동적계획법과 관련은 없(?)지만
피보나치 이야기가 나온 김에...제너레이터를 이용해서 피보나치를 만들 수도 있습니다.
yield와 next를 조합합니다.def fib_generator(): a, b = 0, 1 while True: yield b a, b = b, a + b fib = fib_generator() for _ in range(10): print(next(fib))클로저
클로저(Closure, 폐쇄)를 이용해서 피보나치를 만들 수도 있습니다.
Closer(가까이)가 아님에 주의def fib(): a, b = 0, 1 def function(): nonlocal a, b a, b = b, a + b return b return function fibonacci = fib() for _ in range(10): print(fibonacci())일반항을 이용
F0=0, F1=1, Fn+2=Fn+1+Fn <- 이렇게 표현한 것을 점화식이라 합니다. '여러 항'의 관계에 주목.
일반항은 나무위키를 참고하세요. 수식 표현이 있어서.
아래 파이썬 코드를 봐도 되지만...https://namu.wiki/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4
def fibonacci(n): return int((((1 + 5 ** 0.5) / 2) ** n - ((1 - 5 ** 0.5) / 2) ** n) / 5 ** 0.5) fibonacci(7)반응형