알고리즘 - 최대공약수 / 최소공배수

 

1. 개요

 

2개의 숫자를 입력받았을 때, 최대공약수 / 최소공배수를 구하는 방법을 알아보자.

 

최대공약수 GCD(Greatest Common Divisor)

2개의 숫자가 입력되었을 때, 각각이 가지는 약수 중 공통의 값 중에서 가장 큰 값을 말한다.
ex) 10과 8의 최대공약수는 2이다.

 

최소공배수 LCM(Least Common Multiple)

2개의 숫자가 입력되었을 때, 각각이 가지는 배수 중 공통의 값 중에서 가장 작은 값을 말한다.
최소공배수는 두 수의 곱에 최대공약수를 나누면 구할 수 있다.
ex) 10과 8의 최소공배수는 40이다.

 

이를 코드로 어떻게 구현할 수 있을까? 최대공약수를 구할 때, 1부터 시작하여 두 수 중 작은 수에 도달할 때까지 찾아 가장 큰 공약수를 구할 수도 있다.

하지만 이 방법은 숫자 N, M (N <= M) 이 주어졌을 때, O(N) 만큼의 시간이 소요된다.

따라서, 다른 방법을 써서 더 효율적으로 구할 수 있는데 이것을 유클리드 호제법(Euclidean Algorithm)이라고 한다.

 

유클리드 호제법(Euclidean Algorithm)

2개의 수의 최대공약수를 구하기 위해 쓰이는 알고리즘
2개의 수 중 더 작은 수로 큰 수를 나눈 나머지를 구하고, 작은 수와 나머지 숫자를 각각 큰 수 / 작은 수로 다시 정의하여 나머지가 0이 되면 해당 수를 최대공약수로 결정하는 방법

ex) 735와 1,176의 최대공약수 구하기

① 1176 % 735 = 441 ( %는 나머지 연산 )
② 735 % 441 = 294
③ 441 % 294 = 147
④ 294 % 147 = 0
따라서, 147이 735와 1176의 최대공약수가 된다.

 

 

2. 코드로 구현하기

 

최대공약수와 최소공배수를 구하는 방법은 다음과 같다. 2개의 수를 직접 입력하고 그에 대한 답을 구할 수 있는 코드이다.

package com.test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class GCDandLCM {
    public static void main(String[] args) throws IOException {
        // 2개의 숫자를 하나의 Line에 띄어서 각각 입력 ex) 1176 735
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        // 최대공약수 구하기
        int gcd = GCD(A, B);

        // 최소공배수 구하기 ( 두 값을 곱하고 최대공약수로 나눈다.)
        int lcm = A * B / gcd;

        System.out.println("최대공약수 : " + gcd);
        System.out.println("최소공배수 : " + lcm);
        br.close();
    }
    private static int GCD(int n1, int n2){
        if(n2 == 0){
            return n1;
        } else {
            return GCD(n2, n1 % n2);
        }
    }
}

 

관련 백준 알고리즘 문제는 다음과 같다.

백준 1934 : www.acmicpc.net/problem/1934

백준 2609 : www.acmicpc.net/problem/2609

 

감사합니다.