백준 1629번 행렬 거듭제곱 문제의 원리를 파헤쳐보자

복잡해 보이는 행렬 거듭제곱 문제를 O(log B)의 시간 복잡도로 해결하는 알고리즘에 대해 공부했습니다. 단순 반복이 아닌, 분할정복과 모듈러 연산의 조합이 어떻게 성능 향상을 가져오는지, 그리고 이 원리가 어떻게 풀고자 하는 문제에 적용되는지 이해할 수 있었습니다.

학습 주제

• 주제: 행렬 거듭제곱과 모듈러 연산 최적화
• 대화 제목: 백준 1629번 문제 풀이 및 행렬 거듭제곱 적용
• 학습 날짜: 2026년 1월 31일

질문과 탐구

평소 저는 주어진 문제를 해결하기 위해 기본적인 반복문을 사용하는 방식에 익숙했습니다. 하지만 백준 1629번 문제에서처럼 지수가 매우 커질 경우, 단순 반복은 시간 초과를 피할 수 없다는 것을 경험했습니다. 결국 AI에게 이를 해결할 알고리즘에 대해 질문했고 O(log b)로 해결 가능한 알고리즘이 존재한다는 말에 다음과 같은 질문들로 이어졌습니다.

• a^b % c를 O(b)가 아닌 O(log b)로 계산하는 방법은 무엇인가?
• 핵심 아이디어는 무엇이며, 어떻게 구현되는가?
• 행렬 거듭제곱에도 이 원리를 적용할 수 있는가?
• 행렬 곱셈에서 모듈러 연산은 어떻게 적용해야 정확한가?

이러한 궁금증을 바탕으로, '분할정복 거듭제곱(modular exponentiation)'이라는 알고리즘을 배우게 되었습니다.

핵심 학습 내용

1. 분할정복 거듭제곱: O(log B)

아이디어는 지수 b를 절반씩 줄여나가면서 재귀적으로 계산하는 것입니다.

• 핵심 수학 성질: (A * B) % C = ((A % C) * (B % C)) % C
  이 성질 덕분에 우리는 각 단계마다 모듈러 연산을 적용하여 값의 크기를 제어할 수 있습니다.
• 알고리즘 구조:
  • b가 0이면 1 (또는 단위행렬)을 반환합니다. (기저 조건)
  • b가 짝수라면: A^b = (A^(b/2)) * (A^(b/2))
  • b가 홀수라면: A^b = (A^(b/2)) * (A^(b/2)) * A

이 재귀적인 구조는 지수 b를 절반씩 줄여나가므로, 연산 횟수는 log2(b)에 비례하게 됩니다. 이것이 바로 O(log b)의 시간 복잡도를 달성하는 원리입니다.

// 예시 (모듈러 거듭제곱)
long long modpow(long long a, long long b, long long c) {
    if (b == 0) return 1; // 기저 조건: b가 0이면 1 반환

    long long remainder = modpow(a, b / 2, c); // 지수를 절반으로 나눠 재귀 호출
    remainder = (remainder * remainder) % c;   // 재귀 결과 제곱 후 모듈러 연산

    if (b % 2 == 1) // b가 홀수라면, 마지막에 a를 한 번 더 곱함
        remainder = (remainder * a) % c;

    return remainder;
}

2. 행렬 거듭제곱으로의 확장

이 분할정복 원리는 행렬에도 그대로 적용됩니다. 행렬 곱셈은 교환 법칙은 성립하지 않지만, 결합 법칙은 성립하기 때문입니다.

• 행렬 곱셈: (A * B) * C = A * (B * C)
• 행렬 거듭제곱: A^b를 계산할 때, A 행렬의 곱셈 연산을 반복하는 대신, 위에서 설명한 재귀적인 분할정복 방식을 사용합니다.
  • b=0일 때: 단위행렬(Identity Matrix)을 반환합니다. 단위행렬은 곱셈에 대한 항등원 역할을 합니다.
  • b가 짝수: A^b = (A^(b/2)) * (A^(b/2))
  • b가 홀수: A^b = (A^(b/2)) * (A^(b/2)) * A

이때, 행렬 곱셈 자체는 O(N^3)의 복잡도를 가지지만 (N은 행렬의 차원), 재귀 호출 횟수가 O(log b)이므로 전체 시간 복잡도는 **O(N^3 log b)**가 됩니다. 이는 단순히 b번 행렬을 곱하는 것보다 훨씬 효율적입니다.

3. 모듈러 연산의 올바른 적용

행렬 거듭제곱 과정에서 값이 매우 커질 수 있으므로, 문제에서 요구하는 모듈러 연산을 각 단계마다 올바르게 적용하는 것이 중요합니다.

• 핵심 원리: 모듈러 산술의 성질 (a + b) % c = ((a % c) + (b % c)) % c와 (a * b) % c = ((a % c) * (b % c)) % c
• 올바른 적용: 행렬 곱셈 Z[i][j] = (Z[i][j] + X[i][k] * Y[k][j]) % 1000; 와 같이 각 곱셈 결과와 이전 누적합을 더할 때마다 모듈러 연산을 적용해야 합니다. 단순히 (X[i][k] * Y[k][j]) % 1000만 적용하면 누적합 과정에서 overflow가 발생하거나, 문제에서 요구하는 0~999 범위를 벗어날 수 있습니다.

// 올바른 행렬 곱셈 함수 (mod 1000 적용)
vector<vector<long long>> mat_mul(const vector<vector<long long>>& X, const vector<vector<long long>>& Y) {
    vector<vector<long long>> Z(N, vector<long long>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                // 누적합과 곱셈 모두에 mod 적용
                Z[i][j] = (Z[i][j] + X[i][k] * Y[k][j]) % 1000;
            }
        }
    }
    return Z;
}

이해한 내용

이번 학습을 통해 왜 이러한 알고리즘이 효율적인지에 대한 이해를 얻었습니다.

• 새롭게 알게 된 것:
  • 분할정복이 거듭제곱 문제에 어떻게 적용될 수 있는지.
  • 행렬 곱셈의 성질(결합법칙)을 이용해 재귀적인 계산이 가능하다는 점.
  • 모듈러 연산이 각 단계에서 어떻게 적용되어야 정확한 결과를 보장하는지.
• 이전 지식과의 연결:
  • 기존에 알던 pow(a, b) 함수의 O(b) 복잡도를 O(log b)로 개선하는 원리를 확실히 이해했습니다.
  • 수학 시간에 배웠던 모듈러 산술의 성질이 실제 알고리즘 구현에서 얼마나 중요한 역할을 하는지 체감했습니다.
  • 행렬 곱셈 자체의 복잡도 O(N^3)와 재귀 호출의 O(log B)가 결합하여 O(N^3 log B)라는 복잡도가 도출되는 과정을 명확히 이해했습니다.

추가 학습 계획

이번 학습을 통해 행렬 거듭제곱의 핵심 원리를 파악했지만, 더 깊이 탐구하고 싶은 부분이 있습니다.

• 더 깊이 공부하고 싶은 부분:
  • 행렬 곱셈의 복잡도를 O(N^3)보다 더 빠르게 개선하는 알고리즘 (예: Strassen 알고리즘)에 대해 알아보기.
  • 선형대수학에서 행렬의 다양한 연산들이 어떻게 컴퓨터 알고리즘과 연결되는지 더 깊이 탐구.
• 관련 자료 찾기:
  • 행렬 거듭제곱 관련 알고리즘 강의 영상 및 블로그 글.
  • 각종 코딩 테스트 사이트에서 행렬 거듭제곱을 활용하는 문제 풀이.
  • 선형대수학 교재 또는 온라인 강의 자료.
• 다음 학습 주제:
  • 고급 수학(선형대수, 이산수학 등)을 활용한 문제 해결 기법 탐구.
  • AI 및 머신러닝에서 행렬 연산의 중요성 및 활용 사례 학습.

참고 자료

• ChatGPT와의 대화 내용 (특히 모듈러 산술, 분할정복 거듭제곱, 행렬 연산 관련 부분)
• 백준 1629번 (곱셈) 문제 및 관련 풀이
• C++ vector를 이용한 행렬 구현 및 연산
• 단위행렬(Identity Matrix)의 정의 및 역할

오늘의 학습은 단순히 코드를 익히는 것을 넘어, 알고리즘의 근본 원리를 이해하는 경험이었습니다. 앞으로도 꾸준히 학습하며 블로그에 유익한 내용들을 공유하도록 노력하겠습니다.