[수학/알고리즘] Cramer's Rule, determinant

교점에 별 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/87377

교점을 찾은 후 출력하는 문제였습니다. 처음에는 가감법을 사용해서 풀었지만, 예외 처리와 계수항을 맞추기 위한 과정들이 너무 복잡했습니다. 또한, 들어오는 값의 범위가 -100k ~ 100k이다보니 int를 가볍게 뛰어넘는 값들이 사용됐습니다. 이는 std::lcm을 사용할 때 문제를 발생시켰습니다.

더 효율적으로 정답을 찾을 수 있는 방법은 크래머 공식을 사용하는 것이었습니다.

---

행렬식(Determinant, $\det$)

크래머 공식에 대해 이해하려면 먼저 행렬식에 대해 이해해야 합니다.

(중요)아래 글은 행렬식에 대한 정확한 정의가 아니며, 제가 행렬식을 이해하기 위한 과정입니다. 틀린점에 대해서 피드백을 주시면 감사합니다.

먼저, 행렬식은 정사각 행렬을 스칼라로 바꾸어 주는 함수입니다.

제가 이해한 바로는 행렬식의 결과 값이 모눈종이(좌표계) 격자를 찌그러트리고 늘렸을 때, 변형된 모눈종이가 원본에 비해 얼만큼 변했는가?에 가까운 것 같습니다. 즉, 행렬이 공간을 얼마나 변형시키는가(길이/면적/부피 및 방향의 변화 비율)를 나타내는 수입니다.

쉽게 이해하기 위해 직선을 사용했습니다(이미지의 좌표평면은 2차원이지만, 1차원이라고 생각하고 봐주셔야 합니다). 좌측의 공간에 대해 $det=2$을 적용한 이미지를 예시로 보겠습니다.

이미지 처럼 공간 자체가 확대되었기 때문에, 직선(빨간선)은 실제로 2배 길어진 16의 길이를 갖게 됩니다. (0, 8)까지의 무수한 점의 위치가 (0, 16)까지로 변형되었기 때문입니다. 하지만, 변형된 공간의 관점에서 봤을 때는 여전히 좌표 값은 변하지 않은 상태입니다. 좌표는 기저벡터를 몇개 사용했는가를 의미하기 때문입니다.

이때, 주의해야 할 점은 1개의 공간만 가지고는 어떻게 변형되었는지는 정확히 알 수 없는 것에 유의해야 합니다. 또한, n차원의 길이/면적/부피가 몇 배가 되었는지에 대해 알려주는 것이기 때문에 모든 방향에 $det$을 곱하는 것이 아닙니다.

예를 들어서, 2차원 공간의 사각형에 $det=2$라고 해서 두 방향의 기저에 모두 2를 곱하면 사각형의 넓이는 4배가 됩니다. (그래서 위 예시 이미지를 x축으로만 늘린 것입니다)

또한, 하나의 원본을 기준으로 다른 공간과 비교했을 때 $det$을 통해 변형된 방향와 크기를 알 수 있습니다.

$det$의 부호

행렬식에서 $det$의 부호는 아래와 같은 규칙을 가집니다.

• $det > 0$ → 방향 유지
• $det < 0$ → 방향 반전
• $det = 0$ → 공간이 납작하게 찌그러짐

예를 들어서, $det = -2$인 경우에는 면적은 2배인데 방향이 반전된 것을 의미합니다.

중요한 것은 $det = 0$일때 입니다. 0이 되면 공간이 납작하게 찌그러진 것과 같이 되어 좌표축 하나가 의미를 잃게 됩니다.

행렬식 활용하기

위에서 행렬식은 공간을 얼마나 변형시키는가를 나타내는 수라고 말씀드렸습니다. 이 개념을 이용하면 평행사변형의 넓이도 아주 쉽게 이해할 수 있습니다. 가로와 세로가 각각 1인 단위 정사각형을 특정 행렬로 변환하면 새로운 평행사변형이 만들어지는데, 이때 변화된 넓이 자체가 바로 행렬식의 값($\det$)이 됩니다.

두 2차원 벡터 $a = (a_1, a_2)$와 $b = (b_1, b_2)$가 이루는 평행사변형의 넓이는 두 벡터의 외적 크기, 혹은 삼각함수를 이용해 계산할 수 있습니다.

$\text{넓이} = \vert{}a_1 b_2 - a_2 b_1\vert{}$

이 식을 $2 \times 2$ 행렬 형태로 쓴 것이 바로 행렬식입니다.

$\det \begin{pmatrix} a_1 & b_1 \\ a_2 & b_2 \end{pmatrix} = a_1 b_2 - a_2 b_1$

---

이제 두 일차 방정식(직선)을 보겠습니다.

$\begin{cases} a_1 x + b_1 y = c_1 \\ a_2 x + b_2 y = c_2 \end{cases}$

이 방정식의 목표는 두 직선이 만나는 교점 $(x, y)$를 찾는 것입니다. 이 방정식을 행렬 형태로 바꾸면 다음과 같습니다.

$\begin{pmatrix} a_1 & b_1 \\ a_2 & b_2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} c_1 \\ c_2 \end{pmatrix}$

이것을 벡터의 합 형태로 다시 풀어서 써보면

$x \begin{pmatrix} a_1 \\ a_2 \end{pmatrix} + y \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} = \begin{pmatrix} c_1 \\ c_2 \end{pmatrix}$

이 식을 말로 풀어보면 다음과 같습니다

기반이 되는 두 벡터 $A = \begin{pmatrix} a_1 \ a_2 \end{pmatrix}$와 $B = \begin{pmatrix} b_1 \ b_2 \end{pmatrix}$를 각각 $x$배, $y$배 늘려서 더했더니, 목표 벡터 $C = \begin{pmatrix} c_1 \ c_2 \end{pmatrix}$가 되었다. 이때 배율 $x$와 $y$는 얼마인가?"

즉, $det \ne 0$라는 것은 평행사변형이 생성된다는 것을 의미합니다. 반대로 0이 나온다면 교점이 생성되지 않았음을 의미합니다. 이를 활용해서 제가 예외 처리하기 위해 만들었던 복잡한 코드를 간편하게 해결할 수 있습니다.

크래머 공식을 사용해서 교점 찾기

방금 방법으로 교점 여부를 확인했다면, 크래머 공식을 통해 교점의 정확한 위치를 알아낼 수 있습니다.

다시, 두 개의 1차 함수(직선의 방정식)가 다음과 같이 주어졌다고 가정해 보겠습니다.

$a_1 x + b_1 y = c_1$
$a_2 x + b_2 y = c_2$

이를 행렬의 형태로 변환하면 다음과 같습니다.

$\begin{pmatrix} a_1 & b_1 \\ a_2 & b_2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} c_1 \\ c_2 \end{pmatrix}$

여기서 크래머 공식을 사용하면 행렬식만으로 교점 $(x, y)$를 쉽게 구할 수 있습니다.

1. 기본 행렬식 ($D$): $x, y$의 계수들로 이루어진 행렬식입니다.

   $D = a_1 b_2 - a_2 b_1$

2. $x$를 위한 행렬식 ($D_x$): 기본 행렬의 첫 번째 열(x의 계수)을 결과값 $c_1, c_2$로 바꾼 행렬식입니다.

   $D_x = c_1 b_2 - c_2 b_1$

3. $y$를 위한 행렬식 ($D_y$): 기본 행렬의 두 번째 열(y의 계수)을 결과값 $c_1, c_2$로 바꾼 행렬식입니다.

   $D_y = a_1 c_2 - a_2 c_1$

최종적으로 교점의 좌표는 각 변수의 행렬식을 기본 행렬식으로 나눈 값입니다.

$x = \frac{D_x}{D}, \quad y = \frac{D_y}{D}$

코드

bool inter(int idx1, int idx2, const vector<vector<int>>& line, arg& args) {
    // 오버플로우 방지를 위해 long long 변환
    long long A = line[idx1][0], B = line[idx1][1], E = line[idx1][2];
    long long C = line[idx2][0], D = line[idx2][1], F = line[idx2][2];

    // 1. 분모(det) 계산
    long long det = A * D - B * C;

    // 평행하거나 일치하면 교점 없음
    if (det == 0) return false;

    // 2. 분자 계산
    long long num_x = B * F - E * D;
    long long num_y = E * C - A * F;

    // 3. 정수로 딱 나누어떨어지는지 확인
    if (num_x % det != 0 || num_y % det != 0) return false;

    // 4. 정수 교점 저장
    args.x = num_x / det;
    args.y = num_y / det;

    return true;
}

기존처럼 LCM을 구해서 계수를 맞추거나 $x, y$ 계수가 $0$일 때 분기 처리를 수십 줄 작성하는 대신, 이 공식 하나로 수십 줄의 코드를 몇 줄로 축소하고 안전하게 처리할 수 있었습니다.