행렬제곱1

• 

  행렬 제곱 (정방행렬) <백준10830번 문제> 안녕하세요. 이번에는 행렬의 제곱에 대하여 설명드리겠습니다. 먼저 예를 하나 들어보겠습니다. 행렬 A의 (18,19)승을 구하고 싶다고 하면, 어떻게 계산하는 것이 빠르겠습니까? 가장 먼저 생각하시는것이 순차적으로 A * A 을 구하고 또 A^2 * A ... 이런식으로 하나하나 곱해가는 방식이 가장 먼저 생각이 나실 겁니다!!!! 혹시 여기에서 단서가 있지 않을 까 싶어 노트에 적고 생각을 해보았습니다. 기본적으로 A*A -> A^2 을 구하게 되고 A^2을 가지고 A^2 * A^2 곱하게 되면 지수가 점점 커지는 것을 알 수 있습니다. 행렬읮 제곱을 구할 때 지수가 짝수일 때는 A^2 을가지고 더 시간을 단축시킬 수 있다는 것을 알게되며 홀수 일때는 단순히 홀수-1 => 짝수가 될 수 있는 원리를 생.. Algorithm 2020. 11. 11.