[BOJ] 백준 22490 : 선형 연립 방정식

https://www.acmicpc.net/problem/22940

22940번: 선형 연립 방정식

---

전체 코드

#include <iostream>
using namespace std;

void q_sort(double **x, int col, int start, int end)
{
    if (start >= end)
        return;

    double piv = abs(x[start][col]);
    int i = start + 1;
    int j = end;

    while (i < j)
    {
        while (i <= end && abs(x[i][col]) >= piv)
            i++;
        while (j > start && abs(x[j][col]) <= piv)
            j--;

        if (i < j)
            swap(x[i], x[j]);
        else
            swap(x[j], x[start]);
    }

    q_sort(x, col, start, j - 1);
    q_sort(x, col, j + 1, end);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    double **x = new double *[n];
    for (int i = 0; i < n; i++)
    {
        x[i] = new double[n + 1];
        for (int j = 0; j <= n; j++)
            cin >> x[i][j];
    }

    for (int j = 0; j < n; j++)
    {
        q_sort(x, j, j, n - 1);
        for (int i = j + 1; i < n; i++)
        {
            double rate = x[i][j] / x[j][j];
            for (int k = j; k <= n; k++)
                x[i][k] -= x[j][k] * rate;
        }
    }

    for (int i = n - 1; i >= 0; i--)
    {
        double temp = x[i][i];
        for (int j = i; j <= n; j++)
            x[i][j] /= temp;

        for (int j = i - 1; j >= 0; j--)
        {
            double rate = x[j][i] / x[i][i];
            for (int k = i; k <= n; k++)
                x[j][k] -= x[i][k] * rate;
        }
    }

    for (int i = 0; i < n; i++)
        cout << x[i][n] << " ";
    cout << endl;

    return 0;
}

---

연립일차 방정식 푸는 방법 

선형대수학은 볼때마다 새롭다.

(끝 없이 나오는 가우스...)

 

선형 연립 방정식을 푸는 방법은 가우스 소거법이 대체로 활용 된다.

(단, 아직 일차 방정식밖에 모름ㅎㅎ)

(1) ax + by = c
(2) dx + ey = f

일 때, (2) 다항식에 (1) 다항식을 '빼서' 단항식으로 만드는데 의의가 있다.

(2) 다항식의 x 계수를 없애기 위해  (2) - (1) * (d/a) 를 시행한다.

 ( (2) 다항식 x 의 계수 / (1) 다항식 x 의 계수 )

(1) ax + by = c
(2) dx + ey = f

(3) ( e - (d/a)*b ) y = f - (d/a)*c
(3-1) {( ae - bd ) / a } y = {( af - cd ) / a}

(상세 풀이)

(1) ax + by = c
(2) dx + ey = f

(3) ( d - (d/a)*a ) x + ( e - (d/a)*b ) y = f - (d/a)*c
(3-1) 0 + ( e - (d/a)*b ) y = f - (d/a)*c
  ( e = ae/a , f = af/a )
(3-2) ( ae/a - db/a ) y = af/a - cd/a
(3-2) {( ae - bd ) / a } y = {( af - cd ) / a}

이때 (3) 단항식을 계산하면 아래와 같이 전개 된다.

y = ( cd - af ) / ( bd - ae )

(상세 풀이)

(1) {( ae - bd ) / a } y = {( af - cd ) / a}
(2) y = {( af - cd ) / a} / {( ae - bd ) / a }
(3) y = {( af - cd ) / a} * { a / ( ae - bd )}
(4) y = ( af - cd ) / ( ae - bd )

따라서 x 는 아래와 같이 전개 된다

(1) ax + by = c
(1-1) ax = c - by
(2) y = ( af - cd ) / ( ae - bd )

(3) ax = c - b{( af - cd ) / ( ae - bd )}
(4) ax = c - ( abf - bcd ) / ( ae - bd )
(5) ax = c( ae - bd ) / ( ae - bd ) - ( abf - bcd ) / ( ae - bd )
(6) ax = {( ace - bcd ) - ( abf - bcd )} / ( ae - bd )
(7) ax = ( ace - abf ) / ( ae - bd )
(8) x = ( ce - bf ) / ( ae - bd )

(계수 안없애니까 되게 복잡하네...)

예시를 통해 편하게 알아보자

a = 1, b = 2, c = 8, d = 3, e = 2, f = 12
(1) 1x + 2y = 8
(2) 3x + 2y = 12

[ y = ( af - cd ) / ( ae - bd ) ]
(2-1) y = (1*12 - 3*8) / (1*2 - 3*2)
(2-2) y = (-12) / (-4)
(2-3) y = 3

[ x = ( ce - bf ) / ( ae - bd ) ]
(3-1) x = (8*2 - 2*12) / (1*2 - 2*3)
(3-2) x = (-8) / (-4)
(3-3) x = 2

x = 2 , y = 3

이와 같이 계산 된다

---

이제22490 문제를 풀어보자

 

 

선형연립방정식은 대체로 행렬을 통해 표현한다.

(첨가 행렬이던가...)

$\left(\begin{array}{ccc}a& b& \mathrm{|\; c}\\ d& e& \mathrm{|\; f}\end{array}\right)$

또한 보통은 가우스-조던  소거법이 활용된다.

(해당 설명은 나중에 쓰자...)

(Reduced Row Echelon Form(RREF) 에 대해서 먼저 써야 한다... ㅜㅜ) 

 

이를 이차원 배열 혹은 이중포인터를 통해 값을 받는다

int n;
cin >> n;

double **x = new double *[n];
for (int i = 0; i < n; i++)
{
    x[i] = new double[n + 1];
    for (int j = 0; j <= n; j++)
        cin >> x[i][j];
}

 

일반적으로 피벗을 통한 가우스 소거를 진행하다가 피벗이 0 이 될 경우 행치환을 시행하지만

알고리즘 성능보단 가독성을 위해 행정렬을 먼저 처리했다.

 

quick sort 로직

( 참고로 계수가 0인 경우 후행으로 이동해야 하므로 그냥 절대값 내림정렬로 구현했다. )

void q_sort(double **x, int col, int start, int end)
{
    if (start >= end)
        return;

    double piv = abs(x[start][col]);
    int i = start + 1;
    int j = end;

    while (i < j)
    {
        while (i <= end && abs(x[i][col]) >= piv)
            i++;
        while (j > start && abs(x[j][col]) <= piv)
            j--;

        if (i < j)
            swap(x[i], x[j]);
        else
            swap(x[j], x[start]);
    }

    q_sort(x, col, start, j - 1);
    q_sort(x, col, j + 1, end);
}

행의 계수 값을 기반으로 정렬한 후, 아래 행 계수 빼기

// 열의 값을 기준으로
for (int j = 0; j < n; j++)
{
    // 행을 정렬 한다.
    q_sort(x, j, j, n - 1);
    for (int i = j + 1; i < n; i++)
    {
        double rate = x[i][j] / x[j][j];
        // 행 단위로 기준이 되는 최상위 계수만큼 빼준다
        for (int k = j; k <= n; k++)
            x[i][k] -= x[j][k] * rate;
    }
}

가우스 소거법은 완료 되었고 아래행 부터 역산하면 x, y 값 산출이 가능 하다

 

다만, 더 쉽게 계산하기 위한 가우스-조던 소거법이 있다.

1. 각 행의 계수를 1이 되도록 전체를 나눠준다.

2. 아래행부터 위행으로 이동하며 (위행 계수 / 아래행 계수) 만큼 빼준다

3. 위와 같은 과정을 거칠 경우 아래와 같은 행렬이 완성 된다.

 

$\left(\begin{array}{ccc}1& 0& \frac{bf-ce}{bd-ae}\\ 0& 1& \frac{cd-af}{bd-ae}\end{array}\right)$

for (int i = n - 1; i >= 0; i--)
{
    double temp = x[i][i];
    // 아래행부터 항의 계수가 1이 되도록 나눠준다
    for (int j = i; j <= n; j++)
        x[i][j] /= temp;

    for (int j = i - 1; j >= 0; j--)
    {
        double rate = x[j][i] / x[i][i];
        // 위행의계수에 맨아래행의 계수(1)를 곱하여 빼준다 => 0이 된다
        for (int k = i; k <= n; k++)
            x[j][k] -= x[i][k] * rate;
    }
}

이제 출력하면 된다.

for (int i = 0; i < n; i++)
    cout << x[i][n] << " ";

아우 힘들어