[프로그래머스] 분수의 덧셈 ( feat. 기약분수, 최대공약수, 유클리드 호제법 )

 

 

 

 

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        
        int numerA = numer1 * denom2;
        int numerB = numer2 * denom1;
        
        int denomA = denom1 * denom2;
        int denomB = denom2 * denom1;

        int numerSum = numerA + numerB;
        int denom = denomA;

        for(int i=denom; i>0; i--){
            if(numerSum%i == 0 && denom%i == 0){  
                numerSum = numerSum/i;
                denom = denom/i;
            }
        }
        
        answer[0] = numerSum;
        answer[1] = denom;
        
        return answer;
    }
}

 

 

 

import java.util.Arrays;

public class FractionAddition {

    public static int[] solution(int numer1, int denom1, int numer2, int denom2) {
        // 공통 분모 계산
        int commonDenom = denom1 * denom2;
        
        // 새로운 분자 계산
        int newNumer = numer1 * denom2 + numer2 * denom1;
        
        // 최대공약수 계산
        int gcdValue = gcd(newNumer, commonDenom);
        
        // 기약 분수로 변환
        int reducedNumer = newNumer / gcdValue;
        int reducedDenom = commonDenom / gcdValue;
        
        // 결과 반환
        return new int[] {reducedNumer, reducedDenom};
    }
    
    // 최대공약수를 계산하는 메서드
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        // 테스트 케이스
        System.out.println(Arrays.toString(solution(1, 2, 3, 4)));  // [5, 4]
        System.out.println(Arrays.toString(solution(9, 2, 1, 3)));  // [29, 6]
    }
}

 

 

최대공약수(GCD, Greatest Common Divisor)는 두 수의 공통된 약수 중에서 가장 큰 값을 의미합니다. 주어진 코드에서 최대공약수를 계산하는 메서드는 **유클리드 호제법(Euclidean algorithm)**을 사용하여 구현되었습니다. 이 방법이 왜 최대공약수를 계산하는지에 대해 설명드리겠습니다.

 

 

 

유클리드 호제법의 원리

유클리드 호제법은 두 수 a와 b에 대해 다음과 같은 성질을 이용하여 최대공약수를 구합니다:

• 성질 1: 두 수 a와 b(단, a > b)의 최대공약수는 b와 a % b의 최대공약수와 같습니다.
  • 예를 들어, GCD(48, 18)을 구한다고 가정해봅시다. 이때 48을 18로 나눈 나머지를 구하면, 48 % 18 = 12가 됩니다. 따라서 GCD(48, 18)은 GCD(18, 12)와 같습니다.
• 성질 2: 어떤 수 a가 0이 되면, 다른 수 b가 최대공약수가 됩니다.
  • 예를 들어, GCD(12, 0)은 12가 됩니다. 이는 12가 0이 아닌 가장 작은 수이기 때문입니다.

 

 

 

유클리드 호제법을 이용한 최대공약수 계산 과정

1. 기본 케이스: b == 0인 경우, a가 최대공약수가 됩니다. 이는 더 이상 나눌 수가 없기 때문에 현재 남아 있는 수 a가 최대공약수가 되는 것입니다.
2. 재귀 호출: b가 0이 아닌 경우, GCD(a, b)를 GCD(b, a % b)로 변환하여 재귀적으로 계산합니다. 이 과정을 반복하면 결국 나머지가 0이 되는 시점에 도달하며, 이때 남은 수가 최대공약수가 됩니다.

예제

GCD(48, 18):
    48 % 18 = 12
    GCD(18, 12)
        18 % 12 = 6
        GCD(12, 6)
            12 % 6 = 0
            GCD(6, 0) = 6

이 예제에서 48과 18의 최대공약수를 구하는 과정은 다음과 같습니다:

1. 48을 18로 나눈 나머지는 12입니다. 즉, GCD(48, 18)은 GCD(18, 12)와 같습니다.
2. 18을 12로 나눈 나머지는 6입니다. 즉, GCD(18, 12)은 GCD(12, 6)과 같습니다.
3. 12를 6으로 나눈 나머지는 0입니다. 즉, GCD(12, 6)은 6이 됩니다.

따라서, 48과 18의 최대공약수는 6입니다.

 

 

 

 

코드 분석

public static int gcd(int a, int b) {
    if (b == 0) {
        return a;  // 기본 케이스: b가 0이면, a가 최대공약수
    }
    return gcd(b, a % b);  // 재귀 호출: GCD(a, b) -> GCD(b, a % b)
}

• if (b == 0): 재귀 호출이 멈추는 조건으로, 이 경우 현재의 a가 최대공약수가 됩니다.
• return gcd(b, a % b): 그렇지 않으면, GCD(a, b)는 GCD(b, a % b)와 같다는 성질을 이용하여 재귀적으로 문제를 작게 만듭니다.

이 방법은 수학적으로 증명된 효율적인 알고리즘으로, 두 수의 최대공약수를 매우 빠르게 구할 수 있습니다.

 

 

 

 

프로그래머스