[Java] 분수 합 구하기 / 유클리드 호제법

프로그래머스 문제를 푸는데 두 분수 합을 구해 기약분수의 형태로 나타내고 그 분자와 분모를 순서대로 담은 배열을 return 하는 문제가 나왔다.

앞서 공부할때도 분수의 형태는 잘 다루지 않았기 때문에 기약분수는 어떻게 만들어야 하나 하고 고민하다 찾아보니 클리드 호제법이란 것이 있다는 것을 알았다. 그래서 관련 문제를 정리하며 유클리드 호제법도 같이 정리해 보고자한다.

 

---

[level unrated] 분수의 덧셈 - 120808

문제 설명

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

 

제한 사항

0 <numer1, denom1, numer2, denom2 < 1,000

 

입출력 예

 

---

문제 풀이

먼저 주어진 분수 2개를 더해야 하기 때문에 분모의 합이 저장되는 변수(commDenom)와 분자의 합이 저장되는 변수(sumNumer)를 각각 선언한다.

그리고 최대공약수로 각각 나누어 기약분수의 분모와 분자를 만들어 반환하면 된다.

 

짧게 요약하자면

1. 분수의 합 구하기(분모, 분자 따로)

2. 기약분수 만들기

 

이때 기약분수를 만들때는 유클리드 호제법을 사용해 gcd를 구하면된다.

 

> 유클리드 호제법

- 두 정수 사이에 최대공약수(gcd)를 보다 효과적으로 구하는 것으로, 인류 최초의 알고리즘이다.

 

형식)  gcd(A, B) = gcd(B, A%B)

 

* 증명

G를 A와 B의 최대공약수라고 할 때, A= aG, B= bG 이다.

A= Bq+r 니까 위의 식을 대입하면,

aG= bGq + r

r중심으로 정리하면 r = aG - bGq = (a-bq)G 가 된다.

B=bG, r=(a-bq)G 니까 G가 B와 r의 최대 공약수가 되려면 b와 (a-bq)가 서로소 임을 증명해야한다.

​

만약 서로소가 아니라고 가정을 해보자.

두 수가 서로소가 아니라면 b= mg , a-bq= ng 로 g라는 공약수가 존재한다.

b의 값을 오른쪽 식에 대입하면 a-mgq=ng

정리하면 a= (mq+n)g 이다.

​

우리는 처음에 A와 B 두 수를 A= aG, B= bG (G는 A와 B의 최대공약수) 라고 선언했는데, 즉 a와 b는 서로소라는 의미이다.

근데 아래 식에서 b= mg 이고 a= (mq+n)g 이면 a와 b는 공약수 g를 갖게된다.

따라서 b와 (a-bq)는 서로소이다.

​

 

전체 코드

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int sumNumer = numer1*denom2 + numer2*denom1; //분자합
        int commDenom = denom1*denom2; //공통분모

        int gcd = getGcd(sumNumer, commDenom); //최대공약수
        int[] answer = {sumNumer/gcd, commDenom/gcd};

        return answer;
    }

    private int getGcd(int a, int b){
        if(b==0){
            return a;
        }
        return getGcd(b, a%b);
    }
}

 

 

 

참고 블로그

https://arinnh.tistory.com/74