선형대수 (Linear Algebra)

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 3분 · 838자/단어 #algorithm #math #linear-algebra #matrix

정의

선형대수 (Linear Algebra) 는 벡터 공간 (vector space) 과 선형 변환 (linear transformation) 을 다루는 수학 분야. PS 에서는 행렬 곱셈 (O(N^3)), 행렬 거듭제곱 (O(N^3 log K)), 역행렬 (Gauss-Jordan 소거) 이 90% 의 용례.

문제 상황과 동기

선형 연립방정식 Ax = b 를 풀거나, 상태 전이 행렬의 거듭제곱으로 k 단계 후의 값을 계산.

naive (Cramer): determinant 를 N 번 계산. O(N^4).
행렬 거듭제곱: 행렬 곱셈 log K 번. 총 O(N^3 log K).

핵심 통찰: 행렬 곱셈 C[i][j] = Σ A[i][k] x B[k][j]. ikj 순서로 캐시 효율 극대화.

시각화

핵심 아이디어

행렬 곱셈

mat_mul(A(n x p), B(p x m)):
    C = zero(n, m)
    for i in 0..n-1:
        for k in 0..p-1:
            if A[i][k] != 0:
                for j in 0..m-1:
                    C[i][j] += A[i][k] * B[k][j]
    return C

행렬 거듭제곱

mat_pow(A, e):
    R = I_n
    while e > 0:
        if e & 1: R = mat_mul(R, A)
        A = mat_mul(A, A)
        e >>= 1
    return R

역행렬 (Gauss-Jordan)

[A | I] 를 row reduction 하여 [I | A^-1] 로 변환. 상세는 가우스 소거법 항목 참고.

알고리즘

mat_mul(A, B):
    C = zero(n, m)
    for i = 0..n-1:
        for k = 0..p-1:
            if A[i][k] == 0: continue
            for j = 0..m-1:
                C[i][j] += A[i][k] * B[k][j]; mod if needed
    return C

mat_pow(A, e):
    R = I_n
    while e > 0:
        if e & 1: R = mat_mul(R, A, mod)
        A = mat_mul(A, A, mod)
        e >>= 1
    return R

구현

// ikj 행렬 곱셈 + 분할 정복 거듭제곱
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Matrix = vector<vector<ll>>;

Matrix mat_mul(const Matrix& a, const Matrix& b, ll mod) {
  int n = a.size(), m = b[0].size(), p = b.size();
  Matrix c(n, vector<ll>(m, 0));
  for (int i = 0; i < n; i++)
      for (int k = 0; k < p; k++) if (a[i][k])
          for (int j = 0; j < m; j++)
              c[i][j] = (c[i][j] + a[i][k] % mod * (b[k][j] % mod)) % mod;
  return c;
}

Matrix mat_pow(Matrix a, ll e, ll mod) {
  int n = a.size();
  Matrix r(n, vector<ll>(n, 0));
  for (int i = 0; i < n; i++) r[i][i] = 1;
  while (e) {
      if (e & 1) r = mat_mul(r, a, mod);
      a = mat_mul(a, a, mod);
      e >>= 1;
  }
  return r;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  int n, p, m; cin >> n >> p >> m;
  Matrix a(n, vector<ll>(p)), b(p, vector<ll>(m));
  for (auto& v : a) for (auto& x : v) cin >> x;
  for (auto& v : b) for (auto& x : v) cin >> x;
  ll mod; cin >> mod; ll e; cin >> e;
  auto prod = mat_mul(a, b, mod);
  cout << "product:
";
  for (auto& v : prod) { for (auto& x : v) cout << x << ' '; cout << '
'; }
  auto pw = mat_pow(a, e, mod);
  cout << "power:
";
  for (auto& v : pw) { for (auto& x : v) cout << x << ' '; cout << '
'; }
}

import sys
input = sys.stdin.readline

def mat_mul(a, b, mod):
  n, m, p = len(a), len(b[0]), len(b)
  c = [[0] * m for _ in range(n)]
  for i in range(n):
      for k in range(p):
          if not a[i][k]: continue
          for j in range(m):
              c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod
  return c

def mat_pow(a, e, mod):
  n = len(a)
  r = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
  while e:
      if e & 1: r = mat_mul(r, a, mod)
      a = mat_mul(a, a, mod)
      e >>= 1
  return r

n, p, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [list(map(int, input().split())) for _ in range(p)]
mod = int(input()); e = int(input())
print("product:")
for row in mat_mul(a, b, mod): print(*row)
print("power:")
for row in mat_pow(a, e, mod): print(*row)

import java.util.*;
import java.io.*;
public class Main {
  static long[][] matMul(long[][] a, long[][] b, long mod) {
      int n = a.length, m = b[0].length, p = b.length;
      long[][] c = new long[n][m];
      for (int i = 0; i < n; i++)
          for (int k = 0; k < p; k++) if (a[i][k] != 0)
              for (int j = 0; j < m; j++)
                  c[i][j] = (c[i][j] + a[i][k] % mod * (b[k][j] % mod)) % mod;
      return c;
  }
  static long[][] matPow(long[][] a, long e, long mod) {
      int n = a.length;
      long[][] r = new long[n][n];
      for (int i = 0; i < n; i++) r[i][i] = 1;
      while (e > 0) {
          if ((e & 1) == 1) r = matMul(r, a, mod);
          a = matMul(a, a, mod); e >>= 1;
      }
      return r;
  }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int p = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      long[][] a = new long[n][p], b = new long[p][m];
      for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine());
          for (int j = 0; j < p; j++) a[i][j] = Long.parseLong(st.nextToken()); }
      for (int i = 0; i < p; i++) { st = new StringTokenizer(br.readLine());
          for (int j = 0; j < m; j++) b[i][j] = Long.parseLong(st.nextToken()); }
      long mod = Long.parseLong(br.readLine());
      long e = Long.parseLong(br.readLine());
      StringBuilder sb = new StringBuilder("product:
");
      for (long[] row : matMul(a, b, mod)) {
          for (long x : row) sb.append(x).append(' '); sb.append('
'); }
      sb.append("power:
");
      for (long[] row : matPow(a, e, mod)) {
          for (long x : row) sb.append(x).append(' '); sb.append('
'); }
      System.out.print(sb);
  }
}

stdin

결과

product:
19 22
43 50
power:
37 54
81 118

복잡도

항목	값
행렬 곱셈	O(N^3)
행렬 거듭제곱	O(N^3 log K)
공간	O(N^2)
Strassen	O(N^2.807), threshold ~1000

변형

연산	설명
Strassen	7회 곱셈으로 2x2 블록 곱, O(N^2.807)
희소 행렬	0 인 원소 skip, ikj 순서
LU 분해	A = L x U, 선형 시스템 고속 풀이
Modular 행렬	모든 연산 mod p, p 는 소수

함정

1. 차원 불일치

A(n x p) x B(p x m) 에서 p 가 일치해야 함.

2. ikj vs ijk

k-loop 를 가장 안쪽 (ijk) = 캐시 미스 폭발. ikj 순서가 표준.

3. 단위 행렬

r[i][i] = 1. 생성 후 별도 설정.

4. 오버플로우

C++ 에서 a[i][k] * b[k][j] 가 long long 초과 가능. mod 후 곱 또는 __int128.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 10830	행렬 제곱	-	kokoa-lab
BOJ 11444	피보나치 수 6	-	kokoa-lab
BOJ 2740	행렬 곱셈	-	kokoa-lab
BOJ 11049	행렬 곱셈 순서	-	kokoa-lab