-
58 - (파이썬) 재귀 함수, 피보나치 수, 메모화(memorization)study with Q - 파이썬 2024. 6. 19. 21:24
# 피보나치 수열
: 수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
즉, a_n을 n번째 항이라고 할 때, 다음과 같다.
a_1 = 1
a_2 = 1
a_n = a_{n-1} + a_{n-2} (n>=3인 자연수)
#피보나치 수열 Fibonacci numbers def fbnc(n): if n == 1 or n == 2 : return 1 elif n >= 3 : return fbnc(n-1) + fbnc(n-2) print(fbnc(1)) print(fbnc(2)) print(fbnc(3)) print(fbnc(4)) print(fbnc(5)) print(fbnc(6)) >>> 1 1 2 3 5 8
※ 근디 말여... 숫자가 늘어나면
애는 착한디좀 느려지는 문제가 생겨.. (n이 30 넘어가니까 버벅이네)a_n = a_{n-1} + a_{n-2}니까 자기를 두 번씩 호출하는 함수여서 겁내 느려
그래프와 트리(아마도 수형도 같은 거 일 듯)-전위 순회를 배우면 이해되는 데 암튼 지금은 중복된 계산이 겁나리 많이 걸쳐서 그렇구나 생각하면 돼
🧐 그러면 말이여 중복된 계산을 줄이면 좀 빨라지지 않을까?
어떻게?
1. memo라는 딕셔너리를 만든다
2. a_{n-1} + a_{n-2}을 구하는 과정을 올려서 임시(temporary)라고 저장한다.
3. memo의 n번째에 temporary를 할당한다.
4. temporary라는 값으로 return한다.
더보기memo = {} def fbmm(n): if n == 1 or n == 2 : return 1 elif n >= 3 : temporary = fbmm(n-1) + fbmm(n-2) memo[n] = temporary return temporary print(fbmm(5)) print(memo) >>> 5 {3: 2, 4: 3, 5: 5}
print(memo)에서 피보나치의 3번째 항이 2, 4번째 항이 3, 5번째 항이 5라는 것이 딕셔너리 형태로 저장되있는 것을 볼 수 있음.
이를 활용해서 fbmm(n)을 호출했는데, n이 memo에 있으면 memo에 있는 n을 return해주라고 코드를 추가하면
이렇게...!
memo = {} def fbmm(n): if n in memo: return memo[n] if n == 1 or n == 2 : return 1 elif n >= 3 : temporary = fbmm(n-1) + fbmm(n-2) memo[n] = temporary return temporary print(fbmm(50)) >>> 12586269025
참고로 a_1 = 1, a_2 = 2도 memo에 넣어버리면 코드가 더 간단해진다.
더보기memo = {1: 1, 2: 1} def fbmm(n): if n in memo: return memo[n] elif n >= 3 : temporary = fbmm(n-1) + fbmm(n-2) memo[n] = temporary return temporary print(fbmm(50)) >>> 12586269025
겁나 빠르게 계산 가능
파이썬 튜터로 보면...
더보기memo에 {1: 1, 2: 1}를 넣고 재귀함수로 함수 스택을 쌓은 것을 볼 수 있고
하나하나 쌓여가는 것을 볼 수 있다
이렇게 반복하게 된다...!최신 파이썬에서는 더 간단한 코드도 가능하지만 일단 고급 기술이므로 안 적겠어...
https://replit.com/@wh3308/jaegwineun-dolaoneun-geoya#main.py
'study with Q - 파이썬' 카테고리의 다른 글
60 - (파이썬) 튜플, 이뮤터블 자료, 뮤터블 자료 (0) 2024.06.24 59 - (파이썬) 조기 리턴과 리스트 평탄화하는 재귀 함수 (0) 2024.06.23 57 - (파이썬) 재귀 함수, 팩토리얼 연산 (0) 2024.06.19 56 - (파이썬) 메모리 구조 : 함수의 값 복사와 레퍼런스 복사 (1) 2024.06.15 55 - (파이썬) 메모리 구조: global 키워드 (0) 2024.06.15