프로그래머스 JS: 분수의 덧셈

문제

코드

function solution(denum1, num1, denum2, num2) {
    let topNum = denum1 * num2 + denum2 * num1
    let bottomNum = num1 * num2
	let gcd = 0
    for(let i = 0; i < topNum; i++) {
        if(topNum%i === 0 && bottomNum%i === 0) {
            gcd = i
        }
    }
    return [topNum/gcd, bottomNum/gcd]
}

풀이

1.두 분수의 분모를 공통분모로 만들기 위해 각 분수를 다른 분수의 분모로 곱해준다.
2.분자는 분자끼리 더해 topNum으로 분모는 분모끼리 더해 bottomNum으로 정리한다.
3.분자와 분모를 최대공약수로 나눠야하므로 최대공약수 gcd를 선언한다.
4.분자나 분모의 나머지 값이 0이 될 때 까지 for문을 이용해 최대공약수를 구하기 위한 나누기를 반복한다.
5.분자와 분모를 최대공약수로 나누는 배열을 만들어 반환한다.

더 나은 풀이

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];
}

간략하게 줄인걸 보고 충격먹은 코드다.
개발자에게 수학이 얼마나 중요한지 알 수 있는 경험이 되었다.
fnGCD라는 최대공약수를 찾는 함수를 만들고
아래의 solution에서 fnGCD함수를 재귀함수로 사용한다.

fnGCD는 유클리드 호제법을 이용한 최대공약수 구하는 방법으로
유클리드 호제법을 간단하게 정리하자면 아래와 같다.

1.큰 수(a)를, 작은 수(b)로 나눈다.
2.나눈 수(b)를 나머지로 계속 나눈다.
3.나머지가 0일 경우 나눈 수가 최대 공약수다.

이를 이용해 fnGCD 함수를 분해해 작동원리를 설명해보겠다.

function fnGCD(a, b){ // 여기서 a는 분자들의 합, b는 분모들의 곱이다
	// 삼항연산자에서 %를 했을때 나머지가 있다면 true가 되어 fnGCD(b, a%b)가 실행되고
	// 나머지가 없다면 false가 되어 b가 실행된다.
    return (a%b)? fnGCD(b, a%b) : b;
	// (a%b)를 해서 나머지가 있는 true가 되고 fnGCD(b, a%b)가 실행되면
	// 유클리드 호제법에 따라 b를 a/b의 나머지인 a%b로 나눈다.
	// 이를 나머지가 0이 될 때 까지 반복한다.
	// 0이 된다면 마지막으로 나눈수가 최대공약수가 된다.
}