Level1 최대공약수와 최소공배수

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환해주는 gcdlcm 함수를 완성해 보세요. 배열의 맨 앞에 최대공약수, 그 다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 gcdlcm(3,12) 가 입력되면, [3, 12]를 반환해주면 됩니다.

일단 문제를 풀기 전에 최대공약수 최소공배수에 대한 개념이 미약해서 찾아보고 여기에 대한 알고리즘을 정리한 사이트가 있어서 그 부분을 참조했다.

1. 최대공약수 (Greatest Common Factor, GCF)

두 개 이상의 수가 공통으로 가지고 있는 약수 중 가장 큰 수

8의 약수 : 1, 2, 4, 8

12의 약수 : 1, 2, 3, 4, 6, 12

8과 12의 최대공약수 : 4

2. 최소공배수 (the Least Common Multiple, LCM)

두 개 이상의 수가 공통으로 가지는 배수 중 가장 작은 수

3의 배수 : 3, 6, 9, 12, 15..

5의 배수 5, 10, 15, 20..

3과 5의 최소공배수 : 15

3. 서로소 (relative prime)

1 외의 공약수를 갖지 않는 두 수

ex) 7, 11 는 1 외의 공약수가 없으므로 서로소이다.

4. 최대공약수 구하는 알고리즘

1) 유클리드(Euclidean) 공식 이용

• 큰 수 A를 작은 수 B로 나누어 떨어지면, A, B의 최대공약수는 B

• A를 B로 나누었을 때 나머지가 R이면, A, B의 최대공약수는 R과 B의 최대공약수와 같다.

​ GCM(A,B) = GCM(B,R) / ex) GCM(15,12) = GCM(12,3)

유클리드 공식 이용 알고리즘 순서

a. 두 수 A, B 중 큰 수, 작은 수를 판별한다.

b. 큰 수를 작은 수로 나누어 나머지를 구한다.

​ - if 나머지가 0 : 작은 수가 최대공약수

​ - if 나머지가 0이 아니면 : 나누기 반복

5. 최소공배수 구하는 알고리즘

최소공배수(LCM) = A x B / 최대공약수(GCD) 이므로 위의 최대공약수 알고리즘으로 최대공약수를 구하고 A x B x GCD 를 구하면 됨

A = a x GCD / B = b x GCD (a, b는 서로소)

LCM = a x b x GCD = A x B / GCD

출처 - 최대공약수 최소공배수 구하는 알고리즘 정리

import java.util.Arrays;

public class TryHelloWorld {
    public int[] gcdlcm(int a, int b) {
        int[] answer = new int[2];

        int min = Math.min(a,b);
        int max = Math.max(a,b);
        int mod;
        while (min > 0) {
            mod = max % min;
            max = min;
            min = mod;
        }
        answer[0] = max;
        answer[1] = (a*b)/answer[0]; //최소공배수는 두 수를 곱한 값에서 최대공약수로 나눠주면 최소공배수가 된다.

        return answer;
    }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        TryHelloWorld c = new TryHelloWorld();
        System.out.println(Arrays.toString(c.gcdlcm(3, 12)));
    }
}