콘텐츠로 이동

이진 거듭제곱

이진 거듭제곱(제곱을 이용한 거듭제곱이라고도 합니다)은 음이 아닌 정수 $n$에 대해 $a^n$을 (단순한 방법에 필요한 $O(n)$번의 곱셈 대신) $O(\log n)$번의 곱셈만으로 계산할 수 있게 해 주는 기법입니다.

이 기법은 결합 법칙을 만족하는 모든 연산에 사용할 수 있으므로, 산술과 관련 없는 여러 문제에서도 중요하게 응용됩니다:

$$(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)$$

가장 대표적인 예로 모듈러 곱셈, 행렬 곱셈, 그리고 아래에서 다룰 다른 문제들에 적용됩니다.

알고리즘

$a$를 $n$제곱하는 것은 단순하게 $a$를 $n - 1$번 곱셈하는 것으로 표현됩니다: $a^{n} = a \cdot a \cdot \ldots \cdot a$. 그러나 이 방법은 $a$나 $n$이 클 때 실용적이지 않습니다.

$a^{b+c} = a^b \cdot a^c$이고 $a^{2b} = a^b \cdot a^b = (a^b)^2$입니다.

이진 거듭제곱의 아이디어는 지수의 이진 표현을 이용해 작업을 나누는 것입니다.

예를 들어 $n$을 2진법으로 나타내 봅시다:

$$3^{13} = 3^{1101_2} = 3^8 \cdot 3^4 \cdot 3^1$$

수 $n$은 2진법으로 정확히 $\lfloor \log_2 n \rfloor + 1$자리를 가지므로, 거듭제곱 $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}}$을 알고 있다면 $O(\log n)$번의 곱셈만 수행하면 됩니다.

따라서 이 값들을 빠르게 계산하는 방법만 알면 됩니다. 다행히 수열의 각 원소는 바로 앞 원소의 제곱일 뿐이므로 이는 매우 쉽습니다.

$$\begin{align} 3^1 &= 3 \\ 3^2 &= \left(3^1\right)^2 = 3^2 = 9 \\ 3^4 &= \left(3^2\right)^2 = 9^2 = 81 \\ 3^8 &= \left(3^4\right)^2 = 81^2 = 6561 \end{align}$$

따라서 $3^{13}$의 최종 답을 구하려면 그중 세 개만 곱하면 됩니다($n$에서 대응하는 비트가 켜져 있지 않으므로 $3^2$는 건너뜁니다): $3^{13} = 6561 \cdot 81 \cdot 3 = 1594323$

이 알고리즘의 최종 복잡도는 $O(\log n)$입니다: $a$의 거듭제곱 $\log n$개를 계산한 다음, 그로부터 최종 답을 얻기 위해 최대 $\log n$번의 곱셈을 수행해야 합니다.

다음 재귀적 방법도 같은 아이디어를 표현합니다:

$$a^n = \begin{cases} 1 &\text{if } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{if } n > 0 \text{ and } n \text{ even}\\ \left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{if } n > 0 \text{ and } n \text{ odd}\\ \end{cases}$$

구현

먼저 재귀 공식을 그대로 옮긴 재귀적 방법입니다:

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

두 번째 방법은 재귀 없이 같은 작업을 수행합니다. 이 방법은 루프 안에서 모든 거듭제곱을 계산하고, 그중 $n$에서 대응하는 켜진 비트가 있는 것들을 곱합니다. 두 방법의 복잡도는 같지만, 이 방법은 재귀 호출의 오버헤드가 없으므로 실제로는 더 빠릅니다.

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

응용

어떤 수를 법으로 하는 큰 지수의 효율적인 계산

문제: $x^n \bmod m$을 계산하십시오. 이는 매우 흔한 연산입니다. 예를 들어 모듈러 곱셈 역원을 계산할 때 사용됩니다.

풀이: 나머지 연산은 곱셈에 영향을 주지 않으므로($a \cdot b \equiv (a \bmod m) \cdot (b \bmod m) \pmod m$), 같은 코드를 그대로 사용하되 모든 곱셈을 모듈러 곱셈으로 바꾸기만 하면 됩니다:

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

참고: $b >> m$처럼 큰 경우에는 이 알고리즘을 더 빠르게 만들 수 있습니다. $m$이 양수이고 $\gcd(x, m) = 1$이면, $m$이 소수일 때는 $x^n \equiv x^{n \bmod (m-1)} \pmod{m}$이 성립하고, $m$이 합성수일 때는 $x^n \equiv x^{n \bmod{\phi(m)}} \pmod{m}$이 성립합니다. 이는 페르마의 소정리와 오일러 정리에서 바로 도출되며, 자세한 내용은 모듈러 역원에 관한 글을 참고하십시오.

피보나치 수의 효율적인 계산

문제: $n$번째 피보나치 수 $F_n$을 계산하십시오.

풀이: 더 자세한 내용은 피보나치 수 문서를 참고하십시오. 여기서는 알고리즘의 개요만 살펴보겠습니다. $F_n = F_{n-1} + F_{n-2}$이므로, 다음 피보나치 수를 계산하려면 바로 앞의 두 수만 있으면 됩니다. 이 변환, 즉 $F_i$와 $F_{i+1}$에서 $F_{i+1}$과 $F_{i+2}$로의 전이를 나타내는 $2 \times 2$ 행렬을 만들 수 있습니다. 예를 들어, 이 변환을 $F_0$과 $F_1$ 쌍에 적용하면 $F_1$과 $F_2$로 바뀝니다. 따라서 이 변환 행렬을 $n$제곱하여 $O(\log n)$의 시간 복잡도로 $F_n$을 구할 수 있습니다.

순열을 $k$번 적용하기

문제: 길이가 $n$인 수열이 주어집니다. 이 수열에 주어진 순열을 $k$번 적용하십시오.

풀이: 이진 거듭제곱을 사용하여 순열을 $k$제곱한 다음, 이를 수열에 적용하기만 하면 됩니다. 이렇게 하면 시간 복잡도는 $O(n \log k)$가 됩니다.

vector<int> applyPermutation(vector<int> sequence, vector<int> permutation) {
    vector<int> newSequence(sequence.size());
    for(int i = 0; i < sequence.size(); i++) {
        newSequence[i] = sequence[permutation[i]];
    }
    return newSequence;
}

vector<int> permute(vector<int> sequence, vector<int> permutation, long long k) {
    while (k > 0) {
        if (k & 1) {
            sequence = applyPermutation(sequence, permutation);
        }
        permutation = applyPermutation(permutation, permutation);
        k >>= 1;
    }
    return sequence;
}

참고: 이 문제는 순열 그래프를 만들고 각 사이클을 독립적으로 고려하면 선형 시간에 더 효율적으로 풀 수 있습니다. 그런 다음 $k$를 사이클의 크기로 나눈 나머지를 계산하여, 이 사이클에 속한 각 수의 최종 위치를 구할 수 있습니다.

점 집합에 기하 연산 집합을 빠르게 적용하기

문제: $n$개의 점 $p_i$가 주어질 때, 각 점에 $m$개의 변환을 적용하십시오. 각 변환은 이동, 크기 조절, 또는 주어진 축을 중심으로 주어진 각도만큼의 회전일 수 있습니다. 또한 주어진 변환 목록을 $k$번 적용하는 "루프" 연산도 있습니다("루프" 연산은 중첩될 수 있습니다). 모든 변환을 $O(n \cdot length)$보다 빠르게 적용해야 합니다. 여기서 $length$는 ("루프" 연산을 펼친 후) 적용해야 할 변환의 총 개수입니다.

풀이: 각 종류의 변환이 좌표를 어떻게 바꾸는지 살펴봅시다.

  • 이동 연산: 각 좌표에 서로 다른 상수를 더합니다.
  • 크기 조절 연산: 각 좌표에 서로 다른 상수를 곱합니다.
  • 회전 연산: 변환이 더 복잡하지만(여기서는 자세히 다루지 않겠습니다), 새로운 각 좌표는 여전히 기존 좌표들의 선형 결합으로 나타낼 수 있습니다.

보시다시피, 각 변환은 좌표에 대한 선형 연산으로 나타낼 수 있습니다. 따라서 변환은 다음과 같은 형태의 $4 \times 4$ 행렬로 쓸 수 있습니다.

$$\begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \end{pmatrix}$$

이 행렬에 기존 좌표와 1로 이루어진 벡터를 곱하면, 새로운 좌표와 1로 이루어진 새 벡터가 나옵니다.

$$\begin{pmatrix} x & y & z & 1 \end{pmatrix} \cdot \begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \end{pmatrix} = \begin{pmatrix} x' & y' & z' & 1 \end{pmatrix}$$

(가상의 네 번째 좌표를 왜 도입하는지 궁금하십니까? 그것이 바로 컴퓨터 그래픽스에서 널리 활용되는 동차 좌표의 묘미입니다. 이것이 없다면 이동 연산처럼 좌표에 상수를 더해야 하는 아핀 연산을 단일 행렬 곱셈으로 구현할 수 없습니다. 아핀 변환이 더 높은 차원에서는 선형 변환이 되는 것입니다!)

다음은 변환을 행렬 형태로 나타낸 몇 가지 예입니다.

  • 이동 연산: $x$ 좌표를 $5$만큼, $y$ 좌표를 $7$만큼, $z$ 좌표를 $9$만큼 이동합니다.
$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 5 & 7 & 9 & 1 \end{pmatrix}$$
  • 크기 조절 연산: $x$ 좌표는 $10$배로, 나머지 두 좌표는 $5$배로 조절합니다.
$$\begin{pmatrix} 10 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 \\ 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$
  • 회전 연산: 오른손 법칙에 따라(반시계 방향으로) $x$축을 중심으로 $\theta$도만큼 회전합니다.
$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos \theta & -\sin \theta & 0 \\ 0 & \sin \theta & \cos \theta & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

이제 모든 변환을 행렬로 나타내면, 변환의 연속은 이 행렬들의 곱으로 나타낼 수 있고, $k$번 반복하는 "루프"는 그 행렬의 $k$제곱으로 나타낼 수 있습니다(이는 이진 거듭제곱을 사용하여 $O(\log{k})$에 계산할 수 있습니다). 이렇게 하면 모든 변환을 나타내는 행렬을 먼저 $O(m \log{k})$에 계산한 뒤, 이를 $n$개의 점 각각에 $O(n)$으로 적용할 수 있으므로 전체 복잡도는 $O(n + m \log{k})$입니다.

그래프에서 길이가 $k$인 경로의 개수

문제: 정점이 $n$개인 방향 가중치 없는 그래프가 주어질 때, 임의의 정점 $u$에서 다른 임의의 정점 $v$로 가는 길이 $k$인 경로의 개수를 구하십시오.

풀이: 이 문제는 별도의 글에서 더 자세히 다룹니다. 알고리즘은 그래프의 인접 행렬 $M$($i$에서 $j$로 가는 간선이 있으면 $m_{ij} = 1$, 그렇지 않으면 $0$인 행렬)을 $k$제곱하는 것으로 이루어집니다. 이제 $m_{ij}$는 $i$에서 $j$로 가는 길이 $k$인 경로의 개수가 됩니다. 이 풀이의 시간 복잡도는 $O(n^3 \log k)$입니다.

참고: 같은 글에서는 이 문제의 또 다른 변형도 다룹니다. 간선에 가중치가 있고, 정확히 $k$개의 간선을 포함하는 최소 가중치 경로를 찾아야 하는 경우입니다. 그 글에서 보인 것처럼, 이 문제 역시 인접 행렬의 거듭제곱으로 해결됩니다. 행렬에는 $i$에서 $j$로 가는 간선의 가중치가 들어가며, 그러한 간선이 없으면 $\infty$가 들어갑니다. 두 행렬을 곱하는 일반적인 연산 대신 변형된 연산을 사용해야 합니다. 곱셈 대신 두 값을 더하고, 합 대신 최솟값을 취합니다. 즉, $result_{ij} = \min\limits_{1\ \leq\ k\ \leq\ n}(a_{ik} + b_{kj})$입니다.

이진 거듭제곱의 변형: $m$을 법으로 두 수 곱하기

문제: $m$을 법으로 두 수 $a$와 $b$를 곱하십시오. $a$와 $b$는 내장 자료형에 들어가지만, 그 곱은 64비트 정수에 담기에는 너무 큽니다. 핵심은 큰 수 연산을 사용하지 않고 $a \cdot b \pmod m$을 계산하는 것입니다.

풀이: 앞에서 설명한 이진 구성 알고리즘을 그대로 적용하되, 곱셈 대신 덧셈을 수행하기만 하면 됩니다. 다시 말해, 두 수의 곱셈을 $O (\log m)$번의 덧셈과 2배 곱셈(본질적으로는 덧셈입니다) 연산으로 "전개"한 것입니다.

$$a \cdot b = \begin{cases} 0 &\text{if }a = 0 \\ 2 \cdot \frac{a}{2} \cdot b &\text{if }a > 0 \text{ and }a \text{ even} \\ 2 \cdot \frac{a-1}{2} \cdot b + b &\text{if }a > 0 \text{ and }a \text{ odd} \end{cases}$$

참고: 이 과제는 부동소수점 연산을 사용하여 다른 방법으로 풀 수도 있습니다. 먼저 부동소수점 수를 사용하여 식 $\frac{a \cdot b}{m}$을 계산하고, 이를 부호 없는 정수 $q$로 변환합니다. 부호 없는 정수 연산을 사용하여 $a \cdot b$에서 $q \cdot m$을 빼고, $m$으로 나눈 나머지를 취하면 답을 구할 수 있습니다. 이 풀이는 다소 신뢰하기 어려워 보이지만, 매우 빠르고 구현하기도 매우 쉽습니다. 자세한 내용은 여기를 참고하십시오.

연습 문제