[백준-22940] 선형연립방정식 풀이

들어가며

22940번: 선형 연립 방정식

플레티넘 5짜리 문제이지만 사실 선형대수 개념만 조금 이용하면 간단하게 풀리는 문제입니다. 선형 연립 방정식을 푸는 것은 다양한 방법이 있지만 문제 조건을 봤을때 가우스 소거법을 이용하여 해당 방정식의 Row Echelon Form matrix(REF, 행사다리꼴)을 구하면 방정식의 해를 쉽게 구할 수 있을것입니다. 그런데 REF를 구해서 방정식의 해를 하나씩 구해가는 후진대입법을 사용하기에는 코드 상으로 구하는 과정도 귀찮고 계산양도 많아질거 같아서 그냥 대각 원소들을 1로 가지는 기약행사다리꼴(reduced row echelon form, RREF)을 만들어서 구하는 것이 훨씬 간편할거 같다는 판단을 했습니다. (즉 가우스 조르단 소거법을 사용한 풀이입니다.)

---

풀이

가우스소거법 및 가우스 조르단 소거법에 대한 자세한 개념은 추후 선형대수와 관련한 글을 적을때 자세히 설명하고자 합니다. 오늘은 그냥 아래 방법을 사용하면 선형연립방정식의 해가 나옵니다! 정도만 하고 c++로 작성한 코드에 대해 이야기 하고자 합니다. 

 

1. 선형연립방정식을 행렬(첨가계수행렬)로 나타내기

$$\left\{\begin{matrix}x + 2y = 8\\3x + 2y = 12  \end{matrix}\right. -> \begin{bmatrix}1 & 2 & 8 \\3&  2&  12\\\end{bmatrix}$$

각 변수에 대한 계수를 순서대로 적고 맨 오른쪽 열에 방정식의 결과를 넣어준다. 이 문제에서는 첨가계수행렬이 그대로 입력으로 주어지기 때문에 따로 바꿀 필요는 없다. 입력을 그대로 2차원 배열에 저장해주자!

 

2. 기약행사다리꼴로 나타내기

아래의 세가지 계산(기본행 연산)을 통해 i행 i열의 값은 1이고 i열의 i행을 제외한 나머지 행의 값 (i행 j열 단 i!=j)는 0이 되도록 행렬을 수정한다. 

 

• i행의 모든 원소에 상수 c를 곱한다. $R_i  -> CR_i$
• i행을 i행에 상수 c를 j행에 곱해서 뺀다. $R_i -> R_i - CR_j&
• i행과 j행을 바꾼다. $R_i <->R_j$

3. 2번 연산을 수행 했을 때 가장 오른쪽 열의 값이 방정식의 해가 된다.

 

$$\left\{\begin{matrix}a_1x+b_1y+c_1z=k_1\\a_2x+b_2y+c_2z=k_2\\a_3x+b_3y+c_3z=k_3\end{matrix}\right.$$

방정식이 만약 위와 같은 형식이었을 경우2번 과정을 수행 한 후 행렬은 다음 그림과 같을 거고 이때 방정식의 해는 $x=c_1, y=c_2, z=c_3$가 된다.

 

이 문제에서는 해가 무조건 보장된다고 하였으니 위 방법을 그냥 수행하면 된다. 

---

전체 코드

#include<bits/stdc++.h>
using namespace std;
double matrix[10][10];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		for(int j=0;j<=n;j++) scanf("%lf",&matrix[i][j]);
	}
	for(int i=0;i<n;i++){
		double div = matrix[i][i];
		for(int j=i;j<=n;j++){	
			matrix[i][j]/=div;
		}
		for(int j=0;j<n;j++){
			if(i==j) continue;
			double div = -matrix[j][i];
			for(int k=0;k<=n;k++){
				matrix[j][k]+=matrix[i][k]*div;
			}
		}
	}
	for(int i=0;i<n;i++){
		printf("%.lf ",(matrix[i][n]));
	}
	return 0;
}

(살짝의 자랑이지만 정답처리된 코드들 중에서 내 코드가 메모리 효율적으로도 코드 길이적으로도 최적화가 꽤 잘 된 편이었다.ㅎ)

 

---

마무리하며

오늘은 백준 문제 중에 선형대수 관련 문제에 대한 풀이를 해봤습니다. 이거보다 좀더 까다로운 기약행사다리꼴 문제도 있으니 한번 풀어보시는 것도 추천드려요! (살짝 힌트 드리자면 기본적인 자료형 범위를 넘어가는 답이 나와서 자료형 범위 신경써서 풀어보세용~)

20307번: RREF