본문 바로가기
백준_JAVA

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

by stonage 2023. 6. 15.

 

 

2609번: 최대공약수와 최소공배수

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

www.acmicpc.net

 

 

 

 

 

이 문제는 이전에 직관적인 풀이로 해결한 적이 있었는데 최근 프로그래머스에서 최대 공약수와 최소 공배수를 이용하는 문제를 접했다가 처음보는 풀이법을 확인하고 다시 들여다 보게 되었다. 

 

우선, 이전에 내가 풀이를 했던 방식은 단순히 최대 공약수와 최소 공배수를 찾을 때까지 인자를 하나씩 키우거나 줄이면서 해결하는 방법이었다.

 

private void solution () {
        
    Scanner sc = new Scanner(System.in);

    int a = sc.nextInt();
    int b = sc.nextInt();
	
    // 변수 b에 더 큰 값이 담기도록 사전 처리를 한다.
    if (a > b) {
        int temp = a;
        a = b;
        b = temp;
    }

    int gcd = 0;
    int lcm = 0;
	
    // 더 작은 수를 시작으로 1씩 줄이면서 두 수를 나눈 나머지가 모두 0이라면 최대공약수이다. 
    for (int i = a; i >= 1; i--) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
            break;
        }
    }

    // 더 큰 수에 1부터 1씩 증가시키며 곱해준 수를 더 작은 수로 나눈 나머지가 0이라면 최소공배수이다. 
    for (int i = 1; i * b <= 100000000; i++) {
        if ((i * b) % a == 0) {
            lcm = i * b;
            break;
        }
    }

    System.out.println(gcd + "\n" + lcm);

    sc.close();
}

 

 

 

최소 공배수를 구할 때 반복문이 종료되는 조건으로 설정한 수치인 100,000,000은  입력으로 주어지는 두 수 곱의 최대에서 유래했다. 

얼만큼의 연산 횟수가 필요한지 대략적으로 계산해보면 최대 공약수를 구하기 위한 최대 연산 횟수는 입력으로 주어진 수 중에서 더 작은 수의 크기만큼 필요할 것이고,  최소 공배수의 경우 반복문의 최대 반복 횟수만큼 연산해야 할 수도 있지만 실제로는 대부분 도중에 반복문이 중단될 것이므로 시간 제한 조건에 무난하게 통과하였다. 실제로 출력된 평균 시간은 240ms 이었다. 

 

어찌저찌 해결하긴 했으나 최근에 유클리드 호제법을 사용하여 최대 공약수와 최소 공배수를 더 멋드러지게 구할 수 있는 방법을 알게 되어 간단하게 정리해볼까 한다. 

 

 

 

 

 

유클리드 호제법

 

유클리드 호제법에 대한 증명 및 자세한 설명은 다른 분들이 이미 깔끔하게 정리해둔 자료가 구글에 널려있기에 간단하게 정의 및 구현 방법만 짚어보도록한다. 

유클리드 호제법은 2개의 자연수 또는 두 다항식의 최대 공약수를 구하는 알고리즘의 한 종류이다. 두 자연수 A, B(A > B)가 주어질 때, A를 B로 나눈 나머지를 R이라고 하면 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다.

 

원리와 증명을 잘 정리해둔 블로그가 있어서 링크를 남겨두겠다.

 

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

www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 알

st-lab.tistory.com

 

간단한 원리 정리

더보기

두 자연수 A와 B의 최대 공약수가 d라고 하면 다음과 같이 표현할 수 있다. 

A = ad;

B = bd;

이 때, a와 b는 서로소(최대공약수가 1인 두 수의 관계) 이다. 그리고 A와 B는 다음과 같이 표현할 수 있다.

A = Bq + R; (q = 몫)

R을 좌변에 두고 이항시킨 후, 위 수식을 대입하면 다음과 같다. 

R = A - Bq = ad - bdq = (a - bq)d

즉, d는 A, B 그리고 R의 공약수가 된다. 만약 d가 왜 최대공약수인지 증명까지 함께 확인하고 싶다면 위 블로그를 참고하자.

 

 

 

유클리드 호제법이라는 새로운 알고리즘을 적용해보는 일만 남았다. 재귀 함수를 사용하면 간단하게 구현이 가능하다. 앞서 A와 B의 최대 공약수는 A를 B로 나눈(A > B) 나머지 R과 B의 최대 공약수와 같다고 하였는데, A 를 B로 나누었을 때 나머지가 0이라면 B를 반환하고 그렇지 않다면 B와 R을 인자로 넘기는 재귀호출을 반환하면 된다. 이때 R나머지이기 때문에 언제나 B보다 작다.

 

private int getGcd (int a, int b) {
    	
    if (a % b == 0) return b;

    return getGcd(b, a % b);
}

 

 

 

최소 공배수는 최대 공약수를 알고 있다면 이것보다 더 쉽게 구할 수 있다. 최소 공배수는 두 수의 곱을 두 수의 최대 공약수로 한 번 나눈 결과와 같다. A와  B의 최소 공배수는 앞서 최대 공약수를 설명할 때 사용한 A = ad, B = bd를 사용하여 표현하면 abd (a, b 는 서로소이고 d는 최대 공약수)로 나타낼 수 있다. 이는 A와 B를 곱한 값인 abdd를 최대 공약수 d로 한 번 나눈 값과 같다.

 

private void solution () {

// 입력 시작
    Scanner sc = new Scanner(System.in);

    int a = sc.nextInt();
    int b = sc.nextInt();

// 입력 끝 

	// a >= b가 되도록 사전 처리
    if (a < b) {
        int temp = a;
        a = b;
        b = temp;
    }

	
    // a와 b의 최대 공약수 
    int gcd = getGcd(a, b);
    
    // a와 b를 곱한 값을 최대공약수로 한 번 나누면 최소 공배수를 구할 수 있다. 
    int lcm = a * b / gcd;
    
    
    System.out.println(gcd + "\n" + lcm);

    sc.close();
}


// 두 수의 최대 공약수를 반환하는 함수 
private int getGcd (int a, int b) {

    if (a % b == 0) return b;

    return getGcd(b, a % b);
}

'백준_JAVA' 카테고리의 다른 글

[백준] 10830번 - 행렬 제곱  (1) 2023.06.17
[백준] 1766번 - 문제집  (0) 2023.06.16
[백준] 2252번 - 줄 세우기  (1) 2023.06.11
[백준] 3584번 - 가장 가까운 공통 조상  (0) 2023.06.11
[백준] 15663번 - N과 M (9)  (0) 2023.06.10