[Java] 프로그래머스(level1) - 최대공약수와 최소공배수

Input-1

n = 3, m = 12

Output-1

[3, 12]

Input-2

n = 2, m = 5

Output-2

[1, 10]

문제 풀이

최대공약수와 최소공배수를 구하는 문제이다.

최대공약수(Greatest Common Divisor)란?
0이 아닌 두개이 상의 정수의 공통된 약수중 가장 큰 수이다.

일반적으로 푸는 방식과 유클리드 호제법을 통해 푸는 방식 두가지로 풀어보았다.

일반적인 방식

먼저 최대공약수(GCD)를 구해보자.
두 수의 공약수중 가장 큰 공약수를 구하면 된다.

 // 1. 두수의 약수를 구해 최대공약수를 찾는다.
int low = (n < m) ? n : m; // 두수중 작은수를 저장
int GCD = 0; // 최대 공약수
for(int i=1; i<=low; i++) {
    if(n%i == 0 && m%i == 0) GCD = i;
}

다음으로 최소공배수(LCM)는 더욱 간단하게 구할 수 있다.
두수의 곱에서 최대공약수를 나눠주면 된다.

• n * m / GCD(최대공약수)

// 2. 두수의 공배수 중 최소공배수를 찾는다. 최소공배수 = n*m/max
int LCM = n*m/GCD; // 최소공배수

유클리드 호제법을 통한 방식

일반적으로 최대공약수는 소인수분해 및 소인수들의 곱을 통해 구할 수 있는데,
특정 수의 약수가 매우 많다면, 인수분해 및 두수를 비교하여 곱하는 과정에서 많은 시간이 소요된다.
이 점을 방지한 알고리즘 방식이 바로 유클리드 호제법이다.

유클리드 호제법이란?
두 개의 수가 주어졌을 때 최대공약수를 구하는 알고리즘이다.
두개의 수 A, B가 존재하고, A>B일 때, A, B를 나눈 나머지가 C라면 A와 B의 GCD(최대공약수)는 B와 C의 GCD와 같다.

간단하게 예를 들어보자.
50과 23 두개의 수가 있다고 하자.

1. 두 수중 큰 수는 12이다. A=50, B=23
2. 큰 수를 작은 수로 나눈 나머지를 구한다. A%B = 50%23 = 4
3. C(나머지)를 통해 B를 다시 나눠 나머지를 구한다. 23%4 = 3
4. 나머지가 0이 될 때까지 3번을 다시 반복한다. 4%3 = 1
5. 나머지가 0이 될 때까지 3번을 다시 반복한다. 3%1 = 0
6. 5번에서 나머지가 0이 되었으므로 5번에서의 나눈 수(작은 수)인 1이 최대공약수가 된다.

그렇다면 유클리드 호제법으로 최대공약수를 구하는 과정을 코드로 작성해보자.

static int eucd(int bn, int sn) {
    // bn:큰수, sn:작은수
    int r = bn % sn; // 나머지 수
    if(r == 0) return sn;
    else return eucd(sn, r); // 나머지가 0보다 크면 작은수와 나머지수를 통해 재귀함수 호출
}

bn을 sn으로 나눈 나머지를 r에 저장하는데 r이 0보다 클 경우 재귀함수를 통해 0이 되는 시점의 sn을 반환하는 함수를 작성하였다.
최소공배수는 일반적인 방식 풀이에서와 같은 방법으로 풀이하였으니 생략하였다.

작성코드

일반적인 방식 - 작성코드

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        solution(n,m);
    }
    public static int[] solution(int n, int m) {
        int low = (n < m) ? n : m;
        int GCD = 0;
        for(int i=1; i<=low; i++) {
            if(n%i == 0 && m%i == 0) GCD = i;
        }
        int LCM = n*m/max;
        int[] answer = new int[2];
        answer[0] = GCD;
        answer[1] = LCM;
        return answer;
    }
}

유클리드 호제법을 통한 방식 - 작성코드

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        solution(n,m);
    }
    public static int[] solution(int n, int m) {
        int bn = 0;
        int sn = 0;
        if(n>m) { 
            bn=n; 
            sn=m;
        }
        else {
            bn=m; 
            sn=n;
        }
        int GCD = eucd(bn, sn); // 유클리드 호제법으로 최대공약수 구함
        int LCM = n*m/GCD;
        int[] answer = new int[2];
        answer[0] = GCD;
        answer[1] = LCM;
        return answer;
    }
    static int eucd(int bn, int sn) { // Euclidean algorithm
        int r = bn % sn;
        if(r == 0) return sn;
        else return eucd(sn, r);
    }
}

회고

• 최대공약수를 구하는 알고리즘 중 유클리드 호제법에 대해서 공부를 할 수 있었고, 일반적으로 최대공약수를 구하는 방식보다 실행속도면에서 좋은 패턴임을 알게되었다.