[Programmers] 분수의 덧셈 JS + 최대공약수 + 최소공배수 구하기

문제) 분수의 덧셈
https://school.programmers.co.kr/learn/courses/30/lessons/120808

이번 문제를 풀면서 어떻게 풀지 공책에 써내려가 봤는데.. 막히는 부분이 있었다..

바로 기약분수로 답이 나와야 하는 것!

기약분수로 만들어 내려면 분자와 분모를 그들의 최대공약수로 나누어서 나타내야 하는데, 나는 그 방법을 모른다.

그래서 한 번 공부해 보았다!

최대공약수 구하는 방법(JS)

최대공약수란,
두 수의 공통된 약수 중에서 가장 큰 수를 뜻한다.

여기서 최대공약수를 구하는 좋은 방법이 있는데, 그것은 바로 유클리드 호제법이다.

유클리드 호제법

유클리드 호제법이란,
두 수의 최대공약수를 찾는 가장 간단하고 효율적인 방법이다.

2개의 자연수 또는 정식(整式)의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘의 하나이다.

- 위키백과

1. 두수를 A % B 이렇게 나눠서 나머지(R1) 가 생겼다.
2. 이번에는 B % R1 을 나눠버린다. 그럼 또 나머지(R2) 가 생겼다.
3. 요번에는 R1 % R2 을 나눠버린다. 그럼 또 나머지(R3) 이 생겼다.
4. 여번에는 R2 % R3 을 나눠버렸다. 근데 이번에는 나머지가 0 이다. (즉, 없다.)

👉 그럼 두수 A 와 B 의 최대공약수는 (나머지가 멸종되기전) 마지막 나머지였던 R3 이 된다.

출처: https://devbirdfeet.tistory.com/257 [새발개발자:티스토리]

JS 구현

	//최대공약수 구하기 함수
   function greatest(a, b){
       if(b === 0) return a;
       return greatest(b , a % b);
   }

• b(나머지)가 0이면 a(직전 나머지)를 반환하고 탈출
• b를 앞으로 보내고 a % b 를 나눈 나머지(r)을 매개변수로해서 재귀함수로써 호출
  
  

---

그렇다면 문제 풀이

는 어떻게 했나?

function solution(numer1, denom1, numer2, denom2) {
    let nenom = (numer1 * denom2) + (numer2 * denom1); // 분자
    let numer = denom1 * denom2; //분모
    
    //최대공약수 구하기 함수
    function greatest(a, b){
        if(b === 0) return a;
        return greatest(b , a % b);
    }
    
    return [Math.trunc(nenom / greatest(nenom, numer)), Math.trunc( numer/greatest(nenom, numer))];
}

요렇게 했다.

먼저 분자와 분모의 결과를 변수로 선언(nenom, numer)해 주고, return으로 바로 빼 버렸다.

이때 Math.trunc()를 사용해서 소수점을 버려주었다.

참고) 최소공배수 구하기

최소공배수 구하기
두 수의 곱 / 최대공약수

function lcm(a, b){
	return a * b / greatest(a, b);
}

• 앞서 작성한 최대공약수 함수를 사용

후기

처음에 최대공약수를 떠올리기 전에는 삼항연산자를 이용해서 분모와 분자의 크기 비교를 해야하나.. 싶었었다..ㅋ

유클리드 호제법의 원리를 이해하기는 쉬웠지만 재귀함수가 어려운 나에게는 반복 학습이 답인 걸로!