/<> 백준 22940번 : 선형 연립 방정식 (C언어) - 가우스 소거법

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

 

 

처음으로 플레티넘 문제를 풀어서 기분이 아주 좋았습니다ㅋㅋㅎㅎㅋㅋ (2학년이 끝나서야..ㅠㅠ)

사실 선형대수학을 공부하셨다면, 문제 조건이 해가 모두 자연수이므로 구상 자체는 어렵지 않을 겁니다.

하지만 가우스 소거법이 생소하다면 막막할 수 있습니다. 원리만 알면 문제를 풀 수 있으므로 가우스 소거법에 대해 알아보겠습니다.

코드는 설명 밑에 있습니다.

 

---

가우스 소거법 (Gauss Elimination)

 

 

가우스 소거법이란, 위의 문제처럼 선형 연립 방정식이 주어졌을 때 해를 구할 때 사용하는 방법입니다. 이 때 선형 방정식이란 최고 차항의 지수가 1인 방정식을 말합니다. 중학생 때 처음 함수를 그리면 일차 함수의 경우 직선을 그리잖아요? 그래서 '선형'이라고 부르는 겁니다. 즉 일차 방정식이 여러 개 있는 경우입니다.

문제는 미지수가 X1, X2, X3, ··· , Xn 과 같이 여러 개일 수 있습니다. 이를 간결하게 풀어나가기 위해 가우스 소거법을 사용합니다.

 

용어가 어려워 보일 수 있지만, 사실 중학교 수학때 이미 사용한 원리입니다. 중2였나 중3때 배운 연립방정식의 풀이과정을 예시를 통해 간략하게 보겠습니다.

 

이 방적식을 풀 때 위의 식과 아래 식중 하나를 택해 제거할 미지수를 정합니다. 위의 식에서 X를 제거하겠습니다.

 

이를 통해 미지수 하나만 남은 식을 만들 수 있습니다. 따라서 미지수 하나가 남은 식에서 첫 미지수의 값을 구하고, 아래의 식에 첫 미지수의 값을 대입해 두번 째 미지수의 값을 구합니다. Y의 값이 2이므로 아래 식에 대입하면 2X + 6 = 10, X = 2가 나옵니다.

 

이제부턴 위의 연립방정식에서 식과 미지수의 개수가 늘어난 형태를 다룹니다. 하지만 과정은 비슷하겠죠? 각각의 방정식들을 서로 연산하여 미지수를 제거한 뒤, 순차적으로 미지수의 값을 찾습니다. 다음은 미지수가 4개, 방정식이 4개인 선형 연립 방정식을 예로 보여드리겠습니다.

 

연산을 계속하면서 미지수를 계속 쓰기엔 번거러움이 있습니다. 그래서 연산 시 미지수의 계수와 우변의 값만을 표기합니다.

 

이제 순차적으로 미지수들을 제거합니다. 이 때 제거할 때 사용하는 한 방정식의 해당 미지수의 계수를 피벗, pivot 이라고 부릅니다. 이 피벗을 기준으로 나머지 방정식들의 미지수를 제거합니다. 피벗을 지정하여 X1을 제거해보겠습니다.

 

피벗이 있는 방정식에 각각 -2, 1, 2를 곱해 나머지 방정식들에 더한 후 결과입니다. 보시다시피 미지수 X1이 하나만 남은 것을 볼 수 있습니다. 가우스 소거법은 이 과정을 반복하여 위의 행렬의 계수들을 역삼각형 모양으로 만듭니다. 그럼 다음 피벗은 두 번째 식의 X2의 계수 -2로 정하고 다시 미지수 X2를 제거해보겠습니다.

 

 

피벗이 있는 방정식에 각각 4, 3을 곱해 나머지(맨 위의 방정식은 제외합니다. 밑으로 순차적으로 계산합니다.) 방정식들에 더한 후 결과입니다. 미지수 X2가 하나만 남았습니다. 이를 반복하여 역삼각형 모양으로 만들어보겠습니다.

 

연산을 진행할 때 계산하기 쉬운 형태로 방정식을 바꾸는 게 좋으나 (위의 사진을 예로 들면 두 번째 행은 0 1 0 1 6, 세 번째 행은 0 0 1 -1 -1, 네 번째 행은 0 0 0 1 4) 가우스 소거법의 이해를 위해 생략했습니다. 이제 모든 미지수 제거가 완료되었습니다. 보다시피 행렬이 역삼각형 모양이 되었습니다. 맨 밑의 방정식을 통해 2 * X4 = 8 임을 알 수 있죠. 즉 X4 = 4 입니다. 찾은 미지수를 이용해 맨 아래 방정식에서 위로 순차적으로 대입하여 다음 미지수들의 값을 구합니다. X3 = 3, X2 = 2, X1 = 1 임을 알 수 있습니다!! 이것이 가우스 소거법을 이용한 선형 연립 방정식 풀이입니다. (수작업으로 하니까 힘드네요)

 

---

<코드>

#include <stdio.h>

int main() {
        int n;
        scanf("%d", &n);
        float eq[n][n + 1];
        for(int i = 0; i < n; i++) {
                for(int j = 0; j < n + 1; j++) scanf("%f", &eq[i][j]);
        }

        float sol[n];
        for(int i = 0; i < n; i++) sol[i] = 0;

        for(int i = 0; i < n - 1; i++) { // 가우스 소거
                float pivot = eq[i][i];
                for(int j = i + 1; j < n; j++) {
                        float div = eq[j][i] / pivot;
                        for(int k = i; k < n + 1; k++)  {
                                eq[j][k] -= eq[i][k] * div;
                        }
                }
        }

        for(int i = n - 1; i >= 0; i--) { // 해 구하기
                for(int j = i + 1; j < n; j++) {
                        eq[i][n] -= eq[i][j] * sol[j];
                }
                sol[i] = eq[i][n] / eq[i][i];
        }

        for(int i = 0; i < n; i++) printf("%0.f ", sol[i]);
        printf("\n");
        return 0;
}

 

 

아무리 해가 자연수이라도 피벗을 통해 곱할 때 나누기를 하므로 분수가 나올 것을 감안해 float를 사용합니다. 이후 결과 출력땐 int 형태로 출력합니다. 그리고 인덱스 계산에 주의합시다.