11444 (1) 썸네일형 리스트형 백준 11444 피보나치 수 6 - 파이썬 문제. 풀이. 피보나치를 행렬의 거듭제곱으로 풀 수 있다는 사실을 몰랐었는데 이번 문제를 풀면서 알게되었다. 피보나치를 그냥 계산하면 시간 복잡도가 O(n)을 가지지만 행렬의 거듭제곱을 이용하면 O(logn)의 시간 복잡도를 가지게 된다. 식은 다음과 같다. 소스코드. import sys def Square(b): if b == 1: return matrix temp = Square(b // 2) if b % 2 == 0: result = matrix_multiple(temp,temp) return result elif b % 2 == 1: result = matrix_multiple(temp,temp) result = matrix_multiple(result, matrix) return result #.. 이전 1 다음
