[백준] 2609번: 최대공약수와 최소공배수 [JAVA]

출처: https://www.acmicpc.net/problem/2609

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

---

알고리즘

이번 문제는 최대공약수(GCD, Greatest Common Divisor)와 최소공배수(LCM, Least/Lowest Common Multiple)를 구하는 문제입니다.

입력되는 두 개의 자연수를 num1, num2라고 하면, 

최소공배수는 두 수를 곱한 값을 두 수의 중복된 약수로 이루어진 최대공약수로 나누는 방법(num1*num2/GCD)으로 문제를 풀고,

제가 최대공약수를 구하는 방법은 두 가지로,

1. 두 수를 1부터 [두 개의 숫자 중 작은 수]까지 나눠서 나머지가 0인 값 중 가장 큰 값이 최대공약수이므로 for문을 통해 차례대로 진행하는 방법

 

2. 유클리드 호제법(Euclidean algorithm)을 통해 최대공약수를 구하는 방법

 

1번째 방법은 1부터 차례대로 나눠보는 방법으로 O(N)의 시간복잡도를 가지고 있어 나쁘지 않은 방법이지만

2번째 방법으로 하면 O(logN)의 시간복잡도를 가지므로 좀 더 효율적으로 계산할 수 있습니다.

저는 2번째 방법인 유클리드 호제법을 통해 문제를 풀도록 하겠습니다.

 

유클리드 호제법은 두 수의 최대공약수를 구하는 방법으로 두 수 서로 상대방의 수를 나누어 가면서 구하는 알고리즘입니다.

 

mod연산으로 두 수를 나누고 나머지가 있으면 나눴던 수를 다시 나머지로 나누는 과정을 통해 나머지가 0이 되는 값이 최대공약수가 됩니다. (mod연산: 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산, 100 mod 33 = 1 )

예시로, 1224와 765를 보면,

1224 = 153 x 2 x 2 x 2

765 = 153 x 5

이므로 1224와 765는 최대공약수 153(n)의 배수인 것을 알 수 있습니다.

이 방법을 어떻게 설명하면 좋을지 찾아보다가 이해하기 편하게 그림으로 설명해준 블로그가 있어 그와 비슷하게 만들어 보았습니다.

아래 그림은 한 블록을 n이라고 하고 mod연산을 진행한 과정입니다.

유클리드 호제법, mod연산 과정

이 과정을 코드로 작성합니다.

---

코드

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int num1 = Integer.parseInt(st.nextToken());
    int num2 = Integer.parseInt(st.nextToken());
    int gcd = 0;
    int lcm = 0;

    gcd = gcd(num1, num2); // 최대공약수
    lcm = num1*num2/gcd; // 최소공배수
    System.out.println(gcd);
    System.out.println(lcm);
  }
  //유클리드 호제법
  public static int gcd(int num1, int num2) {
    if(num1%num2==0) 
      return num2;
    else 
      return gcd(num2, num1%num2);
  }
}

---

 

이 글의 알고리즘이나 코드에서 지적할만한 부분은 댓글에 남겨주시면 저에게 많은 힘이 됩니다!