가우스 소거법 (Gaussian Elimination)

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 2분 · 610자/단어 #algorithm #math #gaussian-elimination #linear-algebra

정의

가우스 소거법 (Gaussian Elimination) 은 선형 연립방정식 Ax = b 의 해를 구하거나, 행렬의 역행렬 / rank / determinant 를 계산하는 O(N^3) 알고리즘. 확장 행렬 [A | b] 를 기약 행 사다리꼴 (RREF) 로 변환.

문제 상황과 동기

N 개의 미지수와 N 개의 방정식으로 구성된 선형 시스템 Ax = b 를 풀어라.

naive (Cramer): determinant 계산 O(N!) 또는 O(N^4).
Gauss elimination: 전방 소거로 상삼각 + 후방 대입. O(N^3).
Gauss-Jordan: RREF 로 직접 변환, 역행렬 동시 계산. O(N^3).

핵심 통찰: 행 연산 (swap, scale, add) 은 해집합을 보존하면서 행렬을 단순화한다.

시각화

핵심 아이디어

행 기본 연산

1. row_i <-> row_j          (행 교환)
2. row_i <- c * row_i      (행 스케일, c != 0)
3. row_i <- row_i + c * row_j  (행 더하기)

Gauss-Jordan (RREF 직접)

for col = 0..n-1:
    // Partial pivoting: find max |A[i][col]|, i >= col
    if pivot == 0: continue (singular)
    swap, scale pivot row to 1
    for i = 0..n-1, i != col:
        factor = A[i][col]
        eliminate col i

최종적으로 A = I 가 되고 b 가 해.

알고리즘

gauss(Augmented [A | b]):
    row = 0
    for col = 0..n-1:
        sel = argmax(|A[i][col]| for i = row..n-1)
        if |A[sel][col]| < EPS: continue
        swap(A[row], A[sel]); swap(b[row], b[sel])
        pivot = A[row][col]
        for j = col..n-1: A[row][j] /= pivot
        b[row] /= pivot
        for i = 0..n-1:
            if i == row: continue
            factor = A[i][col]
            for j = col..n-1: A[i][j] -= factor * A[row][j]
            b[i] -= factor * b[row]
        row++
    return b

구현

// Gauss-Jordan, O(N^3)
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  int n; cin >> n;
  vector<vector<double>> a(n, vector<double>(n));
  vector<double> b(n);
  for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) cin >> a[i][j];
      cin >> b[i];
  }
  int row = 0;
  for (int col = 0; col < n && row < n; col++) {
      int sel = row;
      for (int i = row; i < n; i++)
          if (abs(a[i][col]) > abs(a[sel][col])) sel = i;
      if (abs(a[sel][col]) < EPS) continue;
      swap(a[row], a[sel]); swap(b[row], b[sel]);
      double pivot = a[row][col];
      for (int j = col; j < n; j++) a[row][j] /= pivot;
      b[row] /= pivot;
      for (int i = 0; i < n; i++) {
          if (i == row) continue;
          double factor = a[i][col];
          for (int j = col; j < n; j++) a[i][j] -= factor * a[row][j];
          b[i] -= factor * b[row];
      }
      row++;
  }
  for (int i = 0; i < n; i++) {
      cout << (int)round(b[i]);
      if (i + 1 < n) cout << ' ';
  }
  cout << '\n';
}

import sys
EPS = 1e-9
data = sys.stdin.read().strip().splitlines()
n = int(data[0])
mat = [list(map(float, line.split())) for line in data[1:]]
a = [row[:-1] for row in mat]
b = [row[-1] for row in mat]

row = 0
for col in range(n):
  if row >= n: break
  sel = max(range(row, n), key=lambda i: abs(a[i][col]))
  if abs(a[sel][col]) < EPS: continue
  a[row], a[sel] = a[sel], a[row]
  b[row], b[sel] = b[sel], b[row]
  pivot = a[row][col]
  for j in range(col, n): a[row][j] /= pivot
  b[row] /= pivot
  for i in range(n):
      if i == row: continue
      factor = a[i][col]
      for j in range(col, n): a[i][j] -= factor * a[row][j]
      b[i] -= factor * b[row]
  row += 1

print(' '.join(str(int(round(v))) for v in b))

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      double[][] a = new double[n][n];
      double[] b = new double[n];
      for (int i = 0; i < n; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          for (int j = 0; j < n; j++) a[i][j] = Double.parseDouble(st.nextToken());
          b[i] = Double.parseDouble(st.nextToken());
      }
      final double EPS = 1e-9;
      int row = 0;
      for (int col = 0; col < n && row < n; col++) {
          int sel = row;
          for (int i = row; i < n; i++)
              if (Math.abs(a[i][col]) > Math.abs(a[sel][col])) sel = i;
          if (Math.abs(a[sel][col]) < EPS) continue;
          double[] tmp = a[row]; a[row] = a[sel]; a[sel] = tmp;
          double t = b[row]; b[row] = b[sel]; b[sel] = t;
          double pivot = a[row][col];
          for (int j = col; j < n; j++) a[row][j] /= pivot;
          b[row] /= pivot;
          for (int i = 0; i < n; i++) {
              if (i == row) continue;
              double factor = a[i][col];
              for (int j = col; j < n; j++) a[i][j] -= factor * a[row][j];
              b[i] -= factor * b[row];
          }
          row++;
      }
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < n; i++) {
          sb.append((int)Math.round(b[i]));
          if (i + 1 < n) sb.append(' ');
      }
      System.out.println(sb);
  }
}

stdin

결과

1 2 3

복잡도

항목	값
시간 (최악)	O(N^3)
시간 (평균)	O(N^3) - 희소하면 O(N^2) 까지 단축 가능
공간	O(N^2) - 확장 행렬 저장
안정성 (수치)	Partial pivoting 필요. 조건수 크면 오차 증폭

변형

방법	설명
Gauss-Jordan	RREF 직접, 역행렬 동시 계산
LU 분해	A = L·U, 여러 b 재사용 가능
Cholesky	대칭 양정치 전용, 2배 빠름
Modular Gaussian	mod p (prime) 에서 연산

함정

1. Singular 행렬

pivot 이 0 이면 해 없음 또는 무한. 항상 EPS 체크.

2. 수치 오차

double, EPS = 1e-9. N 이 100 이상이고 조건수 나쁘면 1e-6.

3. 정수 역행렬

Gauss-Jordan 으로 역행렬 시 분수 발생. 소수 mod p 에서 modular inverse 로 해결.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 22940	선형 연립 방정식 풀이	-	kokoa-lab
BOJ 11000	(수집 안 됨)	-	kokoa-lab
BOJ 12962	(수집 안 됨)	-	kokoa-lab

참고

이 글의 용어 (3개)

모듈러 역원 (Modular Multiplicative Inverse)algorithm: 정의 정수 a 의 모듈러 역원 (modular multiplicative inverse) 은 을 만족하는 정수 x. 기호로 또는 . 존재 조건: gcd(a, m) = 1 일 때만…
분할 정복을 이용한 거듭제곱 (Exponentiation by Squaring)algorithm: 정의 분할 정복을 이용한 거듭제곱 (Exponentiation by Squaring) 은 을 O(log n) 시간에 계산하는 분할 정복 알고리즘. 같은 모듈러 연산에서 특히 필수…
선형대수 (Linear Algebra)algorithm: 정의 선형대수 (Linear Algebra) 는 벡터 공간 (vector space) 과 선형 변환 (linear transformation) 을 다루는 수학 분야. PS 에서는…