행렬거듭제곱1

• 

  백준 11444 java - 피보나치 수 6 해당 문제는 그냥 우연찮게 맞추게 된 문제이다. 이리 저리 생각하다가 그냥 점화식을 행렬로 만들어볼까? 해서 그냥 만들어본 행렬의 곱이 피보나치수열이길래 행렬거듭제곱을 통해서 풀게 된 문제이다. 1. 1 = O(logN) 시간복잡도를 만들어야하는구나 3. 분할정복이 맞다! 4. 근데 어떻게 하지? 이전 배운 분할 정복은 곱셈, 행렬거듭제곱인데? 5. 행렬로 해볼까? 6. 행렬로 어떻게 피보나치 수열 점화식을 짜지? 7. 이렇게 하면 되려나? -> 이게 되네? 8. 코딩하자! 참고 : 모듈러연산 (A 연산 B) mod p= (A mod p 연산 B mod p) (나눗셈 연산은 페르마 소정리를 이용한.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 24.