Algorithm & Data Structure
[백준] 피보나치 수 6 (11444번) - Python
✅문제 - 피보나치 수 6 (11444번) ✅필요 알고리즘 개념 - 분할 합🔵 자연수 a의 1024제곱을 구하는 상황 ◼ Dynamic Programming이나 재귀를 이용하면 최소 1024번의 연산을 진행해야 한다.◼ (a^2)^2 = a^4 인 성질을 이용하면 a^1024 를 10번의 계산으로 구할 수 있다. 이는 제곱 연산의 분할 합 개념을 이용한 것이다. 🔵 피보나치 수열의 분할 합 개념피보나치 수열을 행렬을 통하여 구할 수 있다.이 개념을 적용하면 피보나치 수열을 다음과 같이 표현할 수 있다.이 때 행렬의 n제곱을 하는 과정에서 위에 말한 분할 합의 개념을 적용하면 행렬의 n제곱을 쉽게 구할 수있다.이를 통해 피보나치 수열의 n항을 쉽게 구할 수 있다. ✅코드import sysinput..
