문제
첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1,
두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다.
두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.
해결
1. 이상적 풀이 (최대공약수 구하기)
function fnGCD(a, b){
return (a%b)? fnGCD(b, a%b) : b;
}
function solution(denum1, num1, denum2, num2) {
let denum = denum1*num2 + denum2*num1;
let num = num1 * num2;
let gcd = fnGCD(denum, num); //최대공약수
return [denum/gcd, num/gcd];
}
나중에 써먹을 일이 있을 수도 있으니, 최대공약수와 최소공배수를 구하는 방법을 정리하도록 하겠다
1) 최대공약수 구하기
function fnGCD(a, b){
return (a%b)? fnGCD(b, a%b) : b;
}
Euclidean GCD 공식에서 유래했다고 한다.
gcd(a,b) = g라고 하자
1. r은 g의 배수이다.
a/b = q...r
a = bq + r
gA = gBq + r
r = g(A-Bq)
2. If a number divides both b & r, it must divide a
b와 r의 divisor을 d라고 부르자
a = bq + r
a = dBq + dR = d(Bq + R)
=> 1과 2를 바탕으로 a와 b의 GCD는 b와 r의 GCD의 문제로 축소시킬 수 있음을 증명할 수 있다
gcd(a,b) = gcd(b,r)
r은 웬만하면 a와 b보다 작기 떄문에 문제를 축소시키 위해서 대신 사용하는건 이해가 되는데,
왜 a가 아니라 b를 사용할까?
왜 gcd(a,r)은 안될까?
그거는 2번 증명과 관련이 있다. 2번 증명을 약간 바꿔보도록 하겠다
3. If a number divides bot a & r, it must divide b
a = bq + r
bq = d(A-R)
보면 b는 정확히 d의 배수기보다는 d/q의 배수이다. 운이 좋으면 d의 배수가 될 수도 있지만, 안되는 케이스도 있다는 소리다.
ex) 15 = 4(3) + 3
보면 3인 d는 4인 b를 나눌수가 없다.
그래서 (a,b)의 divisor은 (a,r)의 divisor와 다르기 때문에 이렇게 대체할 수 없다.
Ternary 식이 말하는거 이해하기
- algorithm stops when a % b === 0
- that means a = bq
- So in that moment, gcd(a,b) = b
2) 최소공배수 찾기
사실 최대공약수 찾았으면 문제 없다.
function fnLCM(a,b) {
const gcd = fnGCD(a,b);
return (a*b)/gcd;
}
function fnGCD(a, b){
return (a%b)? fnGCD(b, a%b) : b;
}
2. 내풀이
- 과하게 반복을 한다
- 일단 두 분수를 기약분수가 아닌 상태로 더하기부터 한다
- 더하고 난 다음 분자와 분모중 더 작은 놈을 기준으로
하나씩 줄여가면서 나누고, 둘 다 나머지가 없으면 실제로 나눠준다
- 1부터 baseline 사이 어디인가 최대공약수가 존재하겠지라는 막연한 생각을 기반으로 한다.
function solution(numer1, denom1, numer2, denom2) {
let numer = (numer1 * denom2) + (numer2 * denom1);
let denom = denom1 * denom2;
const baseline = numer < denom ? numer : denom;
for (let i = baseline; i > 1 ; i-- ){
if (numer % i === 0 && denom % i === 0){
numer = numer / i;
denom = denom / i;
}
}
return [numer, denom];
}