첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.
0 <numer1, denom1, numer2, denom2 < 1,000
numer1 | denom1 | numer2 | denom2 | result |
---|---|---|---|---|
1 | 2 | 3 | 4 | [5, 4] |
9 | 2 | 1 | 3 | [29, 6] |
function solution(denum1, num1, denum2, num2) {
const denum = denum1 * num2 + denum2 * num1;
const num = num1 * num2;
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b)
let least = gcd(denum, num)
let answer = [denum / least , num/least]
return answer
}
처음에는
1 / 2 + 3 / 4 = 1.25 이므로
(소수) 합계를 먼저 구한 후 소수 -> 기약분수로 변환하는 방식을 생각해보았다.
1.25 = 1 + 0.1(1/10) * 2 + 0.01(1/100) * 5
와 같이 쪼개는 방법도 생각해보았는데. 결국 약분해야 하므로 PASS
그 다음으로는 분자, 분모를 구하고
두 수의 최대공약수를 구해서 나누는 방법을 생각했다.
denum = denum1 * num2 + denum2 * num1
, num = num1 * num2
이고
gcd 함수를 생성해서 만약 b가 0 (즉, a%b가 0이면) 최대공약수는 a가 되고,
그렇지 않다면 계속해서 그 나머지와 나누어 나머지를 구하는 것을 반복하는 함수이다.
참고 : 유클리드 호제법 (Euclidean Algorithm)
유클리드 호제법(- 互除法, Euclidean Algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘의 하나이다.
호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.