[알고리즘 - Java] 최대공약수 구하기(유클리드 호제법)

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

제한사항
0 <numer1, denom1, numer2, denom2 < 1,000

입출력 예 설명

• 입출력 예시1
  1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.

• 입출력 예시2
  9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.

내가 푼 알고리즘

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        
        int denom = denom1 * denom2;
        int numer = numer1 * denom2 + numer2 * denom1;
        int gcd = gcd(numer , denom);
        return new int[]{numer / gcd, denom / gcd};
    }
    
    private int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a%b);
    }
}

---

문제접근법

1. 통분하기 위해 공통 분모를 곱한다.
2. 통분한 분자를 계산한다.
3. 분자와 분모의 최대공약수를 계산한다.
4. 기약분수를 최대공약수와 나누어 그 몫을 각각 리턴한다.

💡 주목할 부분은 최대공약수를 계산하는 메서드이다.

// 최대공약수를 계산하는 메서드
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

최대공약수를 계산하는 방법 중 가장 많이 쓰이는 알고리즘이 유클리드 호제법이다.

---

유클리드 호제법이란?

• 두 수의 최대공약수를 효율적으로 구하는 알고리즘
• 고대 그리스의 수학자 유클리드에 의해 발견되어 이름이 붙여짐
• 두 정수 a와 b의 최대공약수(Greatest Common Divisor, GCD)는 a를 b로 나눈 나머지와 b의 최대공약수가 같다.

  즉, GCD(a, b) = GCD(b, a % b)

• 이 알고리즘을 재귀적으로 계속 적용하여 나머지가 0이 되면 그 때의 b는 최대공약수가 된다.
• a를 b로 나눈 나머지가 0이 아니라면, a를 b로 나눈 나머지를 새로운 b로 하고 원래의 b를 새로운 a로 생각해야한다.

예시를 들어 설명해보자!

예를 들어, a=48, b=18이다.
1. a를 b로 나눈 나머지는 12이다.(48%18=12) 이때, 나머지가 0이 아니므로 다음 단계로 진행.
2. 새로운 a는 18, 새로운 b는 12가 된다. 다시 새로운 a를 b로 나누어 나머지를 구하면 18 % 12 = 6이다. 나머지가 0이 아니므로 다시 진행.
3. 새로운 a는 12, b는 6이다. 12%6=0이므로 48과 18의 최대공약수는 6이된다.

---

이걸 알고리즘에 적용하면 이런 코드가 된다.

// gcd() 재귀
int gcd = gcd(numer , denom);

// gcd 메서드 구현 
private int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a%b);
    }

---

이런 알고리즘을 만드는 사람도, 푸는사람도 참 대단한듯! 😂

...ㅎ