가우스 소거법

가우스 소거법은 연립 방정식의 해를 구하는 방법 중 하나로, O(N³) 알고리즘으로 쉽게 구현할 수 있다.

 

구현

기준 문제 : https://www.acmicpc.net/problem/22940

22940번: 선형 연립 방정식

 

#import <stdio.h>
#define NMAX 15
#define SWAP(a,b) (a=a^b, b=a^b, a=a^b)
typedef long long INT;
 
int N;
INT inp[NMAX][NMAX];
 
INT lcm, vi, vj, tot;
INT ans[NMAX];
 
INT abs(INT k) { return k>0 ? k:-k; }
 
INT GCD(INT a, INT b) {
    if(a < b) return GCD(b, a);
 
    if(b == 0) return a;
    else return GCD(b, a%b);
}
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N+1;j++) {
            scanf("%lld", &inp[i][j]);
        }
    }
 
    // 가우스 소거법
    for(int i=1;i<N;i++) {
        if(inp[i][i] == 0) {
            int t = i+1;
            while(t<=N and !inp[t][i]) t++;
 
            for(int jj=1;jj<=N+1;jj++) SWAP(inp[i][jj], inp[t][jj]);
        }
 
        for(int j=i+1;j<=N;j++) {
            if(!inp[j][i]) continue;
 
            // inp[i]에서 inp[j]를 빼서 inp[j][i]의 값을 0으로 만들기
            lcm = inp[j][i]*inp[i][i]/GCD(abs(inp[j][i]), abs(inp[i][i]));
 
            vi = lcm/inp[i][i];
            vj = lcm/inp[j][i];
            for(int k=i;k<=N+1;k++) {
                inp[j][k] = (inp[i][k]*vi) - (inp[j][k]*vj);
            }
        }
 
    }
 
    for(int i=N;i>=1;i--) {
        tot = inp[i][N+1];
        for(int j=N;j>i;j--) tot -= inp[i][j]*ans[j];
 
        ans[i] = tot/inp[i][i];
    }
 
    for(int i=1;i<=N;i++) printf("%lld ", ans[i]);
 
}
/*
6
1 -1 0 0 -1 0 0
0 0 0 -1 1 -1 0
0 0 1 1 0 1 0
4 24 0 0 0 0 80
0 24 1 -3 -2 0 0
0 0 0 3 0 -8 62
ans: 8 2 -6 10 6 -4
*/