[Java] 최대공약수와 최소공배수 - 유클리드 호제법 (Lv. 1)

최대공약수와 최소공배수 - 유클리드 호제법 (Lv. 1)

---

1. 문제

2. 풀이

---

1. 문제

프로그래머스

 

2. 풀이

class Solution {
    int gcd(int n, int m) {
        int r;
        
        while(m > 0) {
            r = n % m;
            n = m;
            m = r;
        }
        
        return n;
    }
    
    public int[] solution(int n, int m) {
        int[] answer = new int[2];

        if (n < m) {
            int temp = n;
            n = m;
            m = temp;
        }
        
        answer[0] = gcd(n, m);
        
        answer[1] = n * m / answer[0];
        
        return answer;
    }
}

 

gcd()는 최대공약수(GCD)를 구하는 유클리드 호제법을 적용한 함수입니다.

 

 

• n을 m으로 나눈 나머지 r을 구합니다.
• n을 m으로, m을 r로 변경합니다.
• m이 0이 될 때까지 이 과정을 반복하면, 마지막으로 남은 n이 최대공약수입니다.

이렇게 최대공약수(GCD)를 구하고 최소공배수(LCM)는 두 수의 곱을 최대공약수로 나누면 구할 수 있습니다.

 

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3