프로그래머스- 분수의 덧셈

 

문제

제한사항 및 입출력 예

 

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = {0, 0};
        
        // 분수의 합 계산
        answer[1] = denom1*denom2;
        answer[0] = numer1*denom2+numer2*denom1;
        
        // 최대공약수 계산 (유클리드 호제법)
        int min = Math.min(answer[0], answer[1]);
        int max = 1;
        
        for (int i = min; i >= 1; i--){
            if(answer[0] % i == 0 && answer[1] % i == 0){
                max = i;
                break;
            }
        }
        
        //값 대입 및 리턴
        answer[0] /= max;
        answer[1] /= max;
            
        return answer;
    }
}

for 반복문으로 푼 코드

 

유클리드 호제법을 이용한 최대공약수 및 최소공배수 구하는 방법

 

최대공약수GCD(Greatest Common Divisor) 구하기

2개의 자연수 a, b(a > b)가 있을 때a를 b로 나눈 나머지를 c라고 하면
a와 b의 최대공약수는 b와 c의 최대공약수와 같다.

 b를 c로 나눈 나머지 c'를 구하고,
다시 c을 c'로 나눈 나머지를 구하는 과정을 반복하여  -> 재귀
나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수 

 

최소공배수LCM(Least Common Multiple)  구하기

두 수 중 어떤 수 하나가 다른 한 수의 약수가 아니면

최소공배수 = a * b /최대공약수