거듭제곱 빠르게 연산하기

Abstract

• 거듭제곱을 연산을 할 때 지수가 매우 클 경우 시간이 오래 걸린다.
• 지수를 2의 거듭제곱 형태로 나누어 표현해 빠르게 연산한다.
• 연습 문제: b/11444 (피보나치 수 6)

1. 거듭제곱 연산

\(A^P\)를 계산하는 가장 직관적인 방법은 A를 P번 곱해야 하는 것으로 시간복잡도는 \(O(P)\)이다. 만약 P가 1억 이상으로 매우 클경우 오래 걸리기 때문에 더 빠른 방법이 필요하다. 바로 지수를 2진수로 변환해 \(O(log_2(\text{지수}))\)의 시간복잡도로 구한다.

\[\begin{split} 7^21 &= 7 * 7 * \cdots * 7 \\ 7^21 &= 7^16 * 7*4 * 7 \\ \end{split}\]

2. b/11444: (피보나치 수 6)

피보나치 수를 구하는 기본적인 방법으로 재귀함수, 반복문, 동적계획법이 있다.

• 재귀함수는 \(O(2^n)\)으로 n이 증가할수록 시간복잡도가 기하급수적으로 증가한다.
• 반복문은 \(O(n)\)으로 가능하지만, k개의 서로 다른 피보나치 수열을 구하기 위해선 \(O(nk)\)의 시간이 소요된다.
• 동적계획법은 \(O(n)\)으로 가능하고, n 보다 작은 다른 피보나치 수열의 값은 \(O(1)\)의 시간복잡도로 빠르게 구할 수 있다.

피보나치를 구하는 또 다른 방법으로는 행렬의 거듭제곱을 사용하는 방법이 있다.

\[\begin{pmatrix} f(n) \\ f(n-1) \\ \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} f(n-1) \\ f(n-2) \\ \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}^{n-2} \begin{pmatrix} f(2) \\ f(1) \\ \end{pmatrix}\]

해당 방법의 시간복잡도는 \(O(log n)\)이다.

문제를 풀 때 모듈러 연산의 3번째 특징을 고려해 너무 큰 수가 matrix에 저장되는 것을 방지해야 한다.

\[\begin{split} &1. (a \ mod \ n + b \ mod \ n) \ mod \ n = (a + b) \ mod \ n \\ &2. (a \ mod \ n - b \ mod \ n) \ mod \ n = (a - b) \ mod \ n \\ &3. (a \ mod \ n * b \ mod \ n) \ mod \ n = (a * b) \ mod \ n \\ \end{split}\]