피보나치 수를 구하는 여러가지 방법 (파이썬)
이 글은 Baekjoon, 피보나치 수를 구하는 여러가지 방법 게시글을 공부하는 용도로 작성하였습니다. 원 게시글이 C/C++로 작성되어 있어서, 필자의 코딩테스트 주력 언어인 Python으로 바꾸어보았습니다.
1단계. 일일이 호출
백준 10870. 피보나치 수 5를 풀 수 있으며, 이 문제에서는 n <= 20
이다.
n = int(input())
def fibo(n):
if n == 0:
return 0
if n == 1:
return 1
return fibo(n-1) + fibo(n-2)
print(fibo(n))
- 시간 복잡도 :
O(2^N)
거의 두배씩 늘어나니까.
2단계. DP(메모이제이션)
백준 2747. 피보나치 수를 풀 수 있으며, 이 문제에서는 n <= 45
이다.
n = int(input())
dp = [0] * (45+1)
def fibo(n):
if n == 0:
return 0
if n == 1:
return 1
if dp[n]:
return dp[n]
dp[n] = fibo(n-1) + fibo(n-2)
return dp[n]
print(fibo(n))
- 시간 복잡도 :
O(N)
실제dp
계산은 한번만 하니까. 나머지는 가져다 쓴다.
3단계. DP(타뷸레이션)
백준 2748. 피보나치 수 2를 풀 수 있으며, 이 문제에서는 n <= 90
이다.
n = int(input())
dp = [0] * (90+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])
원 게시글에서는 n 값이 커지면서 자료형을 long long
으로 변경해야 했지만, C와 달리 파이썬은 BigInt도 지원하기 때문에 다른 자료형을 선언할 필요 없다.
- 2단계와 3단계의 시간 복잡도는
O(N)
으로 동일하기 때문에, 사실상 무슨 알고리즘을 사용하든지 통과할 수 있다.
메모이제이션과 타뷸레이션은 DP(Dynamic Programming)의 대표적인 두 기법이다.
코드를 보면 직관적으로 이해할 수 있듯이, 메모이제이션은 기존 하향식 재귀 코드(1단계)에서 중복으로 계산되는 값만 제거한 하향식 다이나믹 프로그래밍 기법이며, 타뷸레이션은 for문을 사용하여 작은 값부터 계산하면서 올라가는 상향식 다이나믹 프로그래밍 기법이다.
4단계. 피사노 주기
백준 2749. 피보나치 수 3를 풀 수 있으며, 이 문제에서는 n <= 1,000,000,000,000,000,000
이지만 1,000,000으로 나눈 나머지
라는 조건이 있다.
n = int(input())
dp = [0] * (1500000)
dp[1] = 1
for i in range(2, 1500000):
dp[i] = dp[i-1] + dp[i-2]
dp[i] %= 1000000
print(dp[n%1500000])
피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 됩니다. 이를 피사노 주기(Pisano Period)라고 합니다.
나머지 = 10^k
일 때,k > 2
라면, 주기는 항상15 × 10^(k-1)
입니다. 이 사실을 모른다고 해도, 주기를 구하는 코드를 이용해서 문제를 풀 수 있습니다.
위 문제에 피사노 주기를 적용하면 다음과 같다.
-
피보나치 수를
10^6
으로 나눈 나머지는 주기가15*(10^5) = 1500000
이다. -
주기의 길이가 1500000이므로,
N번째 피보나치 수 % 1000000
==N%1500000번째 피보나치 수 % 1000000
이다.
5단계. 행렬과 분할정복
나머지가 커지면 dp 배열의 len도 커져야 하기 때문에, 피사노 주기에도 한계가 있다.
백준 11444. 피보나치 수 6를 풀 수 있으며, 이 문제에서는 n <= 1,000,000,000,000,000,000
로 위 문제와 같지만, 1,000,000,007으로 나눈 나머지
라는 조건에서 위의 dp 배열보다 1,000배 더 긴 배열을 선언해야 하며, 메모리 제한에 걸리기 때문에 피사노 주기를 사용할 수 없다.
이런 식이 나오게 된 과정은 다음과 같다.
1) iteration으로 분할 정복
원 게시글의 코딩 방식이 이 방식이다.
import copy
n = int(input())
def matrix_mul(A, B):
C = [[0] * len(B[0]) for _ in range(len(A))]
for i in range(len(C)):
for j in range(len(C[0])):
for k in range(len(A[0])):
C[i][j] += A[i][k] * B[k][j]
C[i][j] %= 1_000_000_007
return C
if n == 0:
print(0)
exit()
rv = [[1, 0], [0, 1]]
a = [[1, 1], [1, 0]]
while n:
if n%2 == 1:
rv = matrix_mul(rv, a)
a = matrix_mul(a, a)
n //= 2
print(rv[0][1])
2) recursion으로 분할 정복
분할 정복은 보통 recursion을 이용하여 짜기 마련이기 때문에,
recursion을 이용하여 가독성을 높인 코드를 짜보았다.
# "분할 정복을 이용한 거듭제곱"의 의미
# 2**10 == 2**5 * 2**5
# 2**11 == 2**5 * 2**5 * 2 느낌
n = int(input())
def mmul(A, B):
C = [[0] * len(B[0]) for _ in range(len(A))]
for i in range(len(C)):
for j in range(len(C[0])):
for k in range(len(A[0])):
C[i][j] += A[i][k] * B[k][j]
C[i][j] %= 1_000_000_007
return C
if n == 0:
print(0)
exit()
def mpow(a, n):
if n == 1:
return a
a = mpow(a, n//2)
a = mmul(a, a)
if n%2 == 1:
return mmul(a, [[1, 1], [1, 0]])
return a
rv = mpow([[1, 1], [1, 0]], n)
print(rv[0][1])
Author And Source
이 문제에 관하여(피보나치 수를 구하는 여러가지 방법 (파이썬)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoopark/fibonacci저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)