[백준 12020번] LU 분해 (C++)

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

 

요즘 선형대수학을 공부하고 있는데 백준에 예제가 잘 나와있어서 연습하기 참 좋다.

어떤 행렬 A를 하삼각행렬과 상삼각행렬로 분해하는 과정이다.

Ax = b 라는 선형연립방정식을 풀 때 단순히 가우스 소거법을 이용하여 풀어도 되지만, LU분해를 사용하면 훨씬 효율적으로 계산할 수 있다. 

가우스 소거법을 활용한 선형연립방정식의 Time complexity: N³

LU분해를 활용한 선형연립방정식의 Time complexity: N² 

 

LU분해를 하는 과정에서 가우스 소거법이 필요해서 최초의 분해를 하는 데에는 N³의 시간복잡도를 필요로 하지만, 분해는 한번 해 놓으면 다시 할 필요가 없다는 점에서 이득을 볼 수 있다. 한마디로 Ax = b에서 b가 얼마든지 바뀌어도 최초의 계산만 N³이 걸릴 뿐 다음부터는 이미 분해되있는 행렬을 사용하면 되기 때문에  N²의 시간복잡도를 선형연립방정식을 해결할 할 수 있다.

 

L(lower trianguler matrix): Upper trianguler를 만들기 위해서 사용한 기본행연산의 역행렬을 Identity matrix에 곱해 구한다.

U(upper trianguler matrix): 가우스 소거법을 통해 구한다.

 

이 문제에서는 입력으로 주어지는 행렬이 Band가 1인 Matrix만 주어진다고 하였으므로 가우스 소거법도 N²으로 해결할 수 있다.

#include <iostream>
#define endl "\n"
using namespace std;

int n;
double upper[1001][1001], lower[1001][1001];

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	cin >> n;
	for(int i = 0; i < n; i++){
		lower[i][i] = 1;
		for(int j = 0; j < n; j++){
			cin >> upper[i][j];
		}
	}

	if(n==1) {
		cout << -1;
		return 0;
	}
	
	for(int i = 0; i < n; i++){
		double pivot = upper[i][i];
		if(pivot == 0) {
			cout << -1;
			return 0;
		}
		
		double tmp = -(upper[i+1][i]/upper[i][i]);
		for(int j = 0; j < n; j++){
			double val = upper[i][j] * tmp;
			upper[i+1][j] += val;
		}
		lower[i+1][i] = -tmp;
	}
	
	cout.precision(3);
	cout << fixed;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << lower[i][j] << " ";
		}
		cout << endl;
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << upper[i][j] << " ";
		}
		cout << endl;
	}
	
}