크라메르 공식 (Cramer's Rule)

정의

크라메르 공식(Cramer's Rule)이란?

크라메르 공식은 정방행렬(n×n)로 표현되는 연립일차방정식 (Ax=b)의 해를 행렬식(det)만으로 구하는 방법입니다.

전제: det(A) ≠ 0 (해가 유일하게 존재)

det(A)=0이면 해가 없거나(불가능), 해가 여러 개(무한)일 수 있어 크라메르 공식만으로 “유일해”를 만들 수 없습니다.

핵심 메시지

크라메르 공식은 “공식” 자체는 간단하지만, 구현은 결국 행렬식 계산에 달려 있습니다. 코딩테스트에서는 보통 2×2 또는 3×3처럼 작은 차원에서만 실전적으로 쓰입니다.

 

수학 개념

Ax=b에서 x를 “행렬식”으로 푼다

일반형( n×n )

연립방정식 Ax=b에서, A의 i번째 열(column)을 b로 바꾼 행렬을 Aᵢ라고 하면 크라메르 공식은 다음과 같습니다.

xᵢ = det(Aᵢ) / det(A)

여기서 중요한 전제는 det(A) ≠ 0 입니다. 이 조건이 만족될 때만 해가 유일하게 존재하며, 나눗셈이 의미를 갖습니다.

2×2에서의 구체 형태(가장 실전)

다음 연립방정식을 보겠습니다.

a x + b y = e
c x + d y = f

A = [[a, b], [c, d]], b벡터 = [e, f]일 때

det(A) = ad - bc
x = (ed - bf) / (ad - bc)
y = (af - ec) / (ad - bc)

 

알고리즘 관점

언제 크라메르 공식을 쓰고, 언제 피해야 하나

좋은 선택인 경우

차원이 작고(2×2, 3×3), 해의 유일성(det(A)≠0)이 보장되거나 판정 가능한 문제에서 유용합니다. 예를 들어 “직선/평면의 교점”, “2개 방정식 2미지수” 같은 기하 문제에서 자주 등장합니다.

피해야 하는 경우

n이 커지면 det 계산이 비싸고(일반적으로 가우스 소거를 써도 O(n³)), 수치 오차(부동소수점)가 문제될 수 있습니다. 그래서 일반적인 선형계 풀이는 보통 가우스 소거법 / LU 분해를 사용합니다.

코테에서의 실전 결론

2×2는 크라메르 공식이 가장 깔끔하고, 3×3은 상황에 따라 가능하지만 그 이상은 “공식 적용”보다 다른 풀이(소거/DP/기하적 관찰)를 먼저 의심하는 편이 안전합니다.

 

구현

Java 구현 (2×2 / 3×3)

TIP

코테에서 입력이 정수일 때는 부동소수점 오차를 피하기 위해 가능한 한 정수 연산(분자/분모)로 유지하거나, 나눗셈 시점에만 double로 변환하는 편이 안전합니다.

1) 2×2 크라메르 공식 (정수 기반)

public class Cramer2x2 {

    static class Result {
        final boolean unique; // det(A) != 0
        final double x;
        final double y;

        Result(boolean unique, double x, double y) {
            this.unique = unique;
            this.x = x;
            this.y = y;
        }
    }

    // a x + b y = e
    // c x + d y = f
    static Result solve(double a, double b, double c, double d, double e, double f) {
        double det = a * d - b * c; // det(A)
        if (det == 0.0) {
            return new Result(false, Double.NaN, Double.NaN);
        }
        double x = (e * d - b * f) / det; // det(A1)/det(A)
        double y = (a * f - e * c) / det; // det(A2)/det(A)
        return new Result(true, x, y);
    }

    public static void main(String[] args) {
        // 12와 18 예시가 아니라, 단순 연립방정식 예시
        // 2x + y = 5
        // x - y = 1
        Result r = solve(2, 1, 1, -1, 5, 1);
        System.out.println(r.unique); // true
        System.out.println(r.x + ", " + r.y); // x=2, y=1
    }
}

2) 3×3 행렬식(det) + 크라메르(확장 형태)

3×3은 “사루스(Sarrus) 공식”으로 det를 바로 계산할 수 있어, 작은 차원에서는 실전적으로 구현 가능합니다.

public class Cramer3x3 {

    // det of 3x3 matrix using Sarrus rule
    static double det3(double[][] m) {
        // m[0][0] m[0][1] m[0][2]
        // m[1][0] m[1][1] m[1][2]
        // m[2][0] m[2][1] m[2][2]
        double a = m[0][0]*m[1][1]*m[2][2] + m[0][1]*m[1][2]*m[2][0] + m[0][2]*m[1][0]*m[2][1];
        double b = m[0][2]*m[1][1]*m[2][0] + m[0][0]*m[1][2]*m[2][1] + m[0][1]*m[1][0]*m[2][2];
        return a - b;
    }

    static double[][] replaceCol(double[][] A, double[] b, int col) {
        double[][] M = new double[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) M[i][j] = A[i][j];
            M[i][col] = b[i];
        }
        return M;
    }

    // Ax=b, returns {x,y,z} when det(A) != 0, else null
    static double[] solve(double[][] A, double[] b) {
        double detA = det3(A);
        if (detA == 0.0) return null;

        double detX = det3(replaceCol(A, b, 0));
        double detY = det3(replaceCol(A, b, 1));
        double detZ = det3(replaceCol(A, b, 2));

        return new double[]{ detX/detA, detY/detA, detZ/detA };
    }

    public static void main(String[] args) {
        double[][] A = {
            { 2, 1, -1 },
            { -3, -1, 2 },
            { -2, 1, 2 }
        };
        double[] b = { 8, -11, -3 };

        double[] ans = solve(A, b);
        if (ans == null) {
            System.out.println("No unique solution (det(A)=0).");
        } else {
            System.out.println(ans[0] + ", " + ans[1] + ", " + ans[2]); // 2, 3, -1
        }
    }
}

 

요약

체크리스트로 마무리

CHECK

✅ 전제: det(A) ≠ 0이면 해가 유일

✅ 공식: xᵢ = det(Aᵢ) / det(A)

✅ 실전: 코테에서는 보통 2×2/3×3에서만 깔끔

✅ 주의: det(A)=0이면 해가 없거나 무한(유일해 불가)