[바미] 수학은 비대면강의입니다

문제

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

19532번: 수학은 비대면강의입니다

---

코드 

const input = require('fs').readFileSync('/dev/stdin').toString().split(' ');
const [a, b, c, d, e, f] = input.map(Number);

// 계수 행렬의 결정자
const delta = a * e - b * d;

// x와 y에 대한 결정자
const deltaX = c * e - b * f;
const deltaY = a * f - c * d;

// x와 y의 해를 계산
const x = deltaX / delta;
const y = deltaY / delta;

console.log(`${x} ${y}`);

문제 해설

이 문제는 두 개의 선형 연립방정식을 해결하면 됩니다.

 

 

현재 문제에서 주어진 방정식은 아래와 같습니다.

이를 행렬로 나타내면 아래와 같이 표현됩니다.

이 문제는 x와 y값을 찾는 것으로, 이는 기본적인 선형 대수학의 문제 중 하나죠.

주어진 입력에서 방정식의 계수 a,b,c,d,e,f를 이용하여 x와 y를 계산하는 형태입니다. 주어진 문제의 조건에 따르면 해는 유일하게 존재하고, 정수 범위 내에 있음을 알 수 있습니다.

 

이 문제는 크래머의 법칙을 사용하여 x와 y를 해결하는 방법이 있습니다.

여기서 △는 주 계수 행렬의 결정자(deteminant)이며 △x와 △y는 각각 x와 y에 대한 결정자를 의미합니다.

주어진 조건에 따라 x와 y는 항상 정수이므로 △는 x와 y의 계산에서 나누어 떨어지는 값으로 주어져야 합니다.

 

그래서 위 JS코드처럼 입력된 계수를 사용하여 두 변수 x와 y의 값을 정확히 계산하고 출력하도록 만들어 풀었습니다.

크래머의 법칙(Cramer's Rule)은 선형 대수학에서 연립 일차방정식을 해결하기 위한 방법 중 하나입니다. 이 법칙은 각 변수에 대한 해를 구할 때 주어진 선형 방정식 시스템의 계수 행렬의 결정자(determinant)를 사용합니다. 크래머의 법칙은 각 변수의 값을 결정자를 통해 직접 계산할 수 있게 해주며, 특히 방정식 시스템의 해가 유일하게 존재할 때 유용합니다.

시간 복잡도

이 때 입력을 읽고 각 값을 정수로 변환하는 작업은 입력 크기에 선형적으로 비례하게 되는데 지금의 경우 상수 개수(6개의 정수)이므로이 부분의 시간 복잡도는 0(1)이 됩니다.

 

그리고 △, △x, △y의 계산은 각각 고정된 수의 곱셈과 덧셈/뺄셈을 포함하므로 이 부분의 시간 복잡도와 결과를 계산하고 출력하는 부분도 고정된 수의 연산만 필요하기 때문에 역시 O(1)이 됩니다.

 

그렇기 때문에 전체 프로그램의 시간 복잡도는 O(1)이 됩니다. (모든 입력이 고정 크기, 계산도 몇 개의 정수 연산으로 제한 되기 때문.)

공간 복잡도

6개의 정수(a,b,c,d,e,f)를 저장하는공간과 결정자와 결과를 계산하는 데 필요한 몇 개 의 추가 변수( △, △x, △y, x,y)가 모두 고정된 수의 공간을 차지하기 때문에 공간 복잡도는 O(1)이 됩니다.