최대공약수와 최소공배수

문제 설명

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

제한 사항

두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1

위의 설명과 같습니다.

입출력 예 #2

자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

Solution

1

import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        int max = Math.max(n, m);
        int min = Math.min(n, m);
        
        List<Integer> maxDivisorList = new ArrayList<Integer>();
        List<Integer> minDivisorList = new ArrayList<Integer>();
       
        // 각각의 약수 구하기
        getSubMultiple(maxDivisorList, max);
        getSubMultiple(minDivisorList, min);
        
        // 최대공약수 구하기
        int gcd = 0;
        
        for(int i = 0; i < maxDivisorList.size(); i++) {
            for(int j = 0; j < minDivisorList.size(); j++) {
                if(maxDivisorList.get(i)%minDivisorList.get(j)==0) {
                    gcd = minDivisorList.get(j);
                    break;
                }
            }
            if(gcd != 0) break;
        }
        
        // 최소공배수 구하기
        boolean flag = true;
        int lcm = 0;
        int val = max;
        int i = 1;
        
        while(flag) {
            if(max%min==0) {
                lcm = max;
                flag = false;
            } else {
                i++;
                max = val * i;
            }
            
        }
        
        answer[0] = gcd;
        answer[1] = lcm;
        
        return answer;
    }
    
    public void getSubMultiple (List<Integer> DivisorList, int val) {
        for(int i = val; i > 0; i--) {
            if(val%i==0) {
                DivisorList.add(i);
            }
        }
    }
}

2

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        int max = Math.max(n, m);
        int min = Math.min(n, m);
        
        answer[0] = getGcd(max, min);
        answer[1] = max * min / answer[0];
        
        return answer;
    }
    
    public int getGcd(int max, int min) {

        if(max%min == 0) return min;
        else return getGcd(min, max%min);

    }
}

Feedback

이 문제의 경우 재귀함수를 사용한 유클리드 호제법을 몰랐기에 생각나는대로 풀 수 밖에 없었다.
하지만 코딩 테스트는 항상 실전처럼 봐야한다.

유클리드 호제법

• 유클리드 알고리즘이라고도 하며, 명시적으로 기술된 가장 오래된 알고리즘으로 알려져 있다.
• 두 개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘이다.
• 두 개의 자연수(또는 정식) a, b에 대하여 (단, a > b), a를 b로 나눈 나머지를 r이라고 한다면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

증명

$a = bq + r(0 \le r < b)$

(a, b) 를 a와 b의 최대공약수라 한다면,

$(a, b) = d$

$a = d\alpha, b = d\beta$

로 표현할 수 있고, 이때 $\alpha$와 $\beta$는 서로소이다.
이를 이용하여 위의 식을 풀어보면,

$a = bq + r$

$\Rightarrow d\alpha = d\beta q + r$

$\Rightarrow d\alpha - d\beta q = r$

$\Rightarrow d(\alpha - \beta q) = r$

위에서 b = d$\beta$라고 하였으므로, 아래와 같이 표현할 수 있고,

$\Rightarrow r = d(\alpha - \beta q), b = d\beta$

이는 위에서 a와 b를 d에 관하여 풀이한 것과 같으므로, 결국 $\alpha-\beta q$와 $\beta$가 서로소인 것을 증명한다면, a와 b의 최대공약수인 d가 r과 b의 최대공약수가 될 수 있다는 것을 증명할 수 있다.

$\alpha-\beta q$와 $\beta$가 서로소가 아니라고 가정하고 증명했을 때, 이 명제가 거짓이라면 $\alpha-\beta q$와 $\beta$는 서로소이다. (수학적 귀류법)

$\alpha-\beta q = tx, \beta = ty$

라고 할때, 1보다 큰 최대공약수 t가 존재한다면 $\alpha-\beta q$와 $\beta$는 서로소가 아니다.

$\alpha-\beta q = tx$

$\Rightarrow \alpha - tyq = tx$

$\Rightarrow \alpha = tyq + tx$

$\Rightarrow \alpha = t(yq + x)$

로 정리할 수 있고, 이때

$\alpha = t(yq + x), \beta = ty$

이므로 $\alpha$와 $\beta$는 서로소이면서 동시에 공약수 t를 갖게되므로 모순이 발생한다. 따라서 앞서 가정한 명제는 거짓이 되므로 $\alpha-\beta q$와 $\beta$는 서로소이다. 결과적으로 a와 b의 최대공약수가 곧, b와 r의 최대공약수와 같다.