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

문제

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

입력

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

출력

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

예제 입력 1 복사

24 18

예제 출력 1 복사

6
72

 

 

문제 분석

1. 최대공약수 d

1-1. 입력받은 수들의 약수 구하기

1-2. 둘의 공통 약수 중 제일 큰 값이 최대공약수 

 

2. 최소공배수 m

2-1. 입력받은 수 / 최대공약수를 각각 n, k이라고 한다면

2-2. 최소공배수 m = 최대공약수 d * n * k

 

 

코드 구현

import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int num1 = kb.nextInt();
		int num2 = kb.nextInt();
		// 약수 담을 배열
		ArrayList numArr1 = new ArrayList<>();
		ArrayList numArr2 = new ArrayList<>();
		
		// 1. 최대공약수 d
		// 1-1. 입력 받은 수들의 약수 구하기
		for(int i=1; i<=num1; i++) {
			if(num1 % i == 0) {
				numArr1.add(i);
			}
		}
		for(int i=1; i<=num2; i++) {
			if(num2 % i == 0) {
				numArr2.add(i);
			}
		}
		// System.out.println(numArr1); [1, 2, 3, 4, 6, 8, 12, 24]
		// System.out.println(numArr2); [1, 2, 3, 6, 9, 18]
		
		// 1-2. 둘의 공통약수 중 제일 큰 값이 최대공약수 
		int max = Integer.MIN_VALUE;
		for(int j=0; j<numArr1.size(); j++) {
			for(int k=0; k<numArr2.size(); k++) {
				if(numArr1.get(j) == numArr2.get(k)) {
					// ........
				}	
			}
		}
		

	}

}

문제 분석을 할 때는 짧게 끝날 줄 알았는데 막상 코드 구현을 시작하니 생각보다 많은 줄이 필요하다는 것을 깨닫고

이 방법보다 효율적인 코드를 찾기 위해 구글 서칭을 시작하였습니다.

 

그러다

유클리드 호제법을 이용해서 최대공약수를 구한 후, 간단한 연산을 통해 최소공배수를 구하는 방법을 알게 되었습니다. 

 

 

---

 

 

최대공약수 GCD (Greatest Common Divisor)

우리가 알고 있는 최대공약수의 정의는

"A와 B 두 수가 주어지면 A의 약수들을 모두 구하고, B의 약수들을 모두 구한 뒤 공통된 약수들만 찾아내어 약수들의 곱으로 다시 나타내 준다."입니다.

이를 유클리드 호제법 알고리즘을 통해 구현할 수 있습니다. 

 

💡 유클리드 호제법 알고리즘
두 수 a, b ∈ ℤ이고, r = a mod b이다. (r = a % b)
이때 r은 (0 ≤ r < b)이고, a ≥ b이다.
 
이때 a와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다.
GCD(a, b) = GCD(b, r)

 

방법은 크게 두 가지가 있습니다.

1. 반복문

2. 재귀

 

// 최대공약수 반복문 방식
int gcd(int a, int b) {
	
	while(b != 0) {
		int r = a % b;	
        
		// GCD(a, b) = GCD(b, r)
		a = b;		
		b = r;
	}
	return a;
}
 
// 최대공약수 재귀 방식
int gcd(int a, int b) {
	if(b == 0) return a;
	// GCD(a, b) = GCD(b, r) (r = a % b)
	return gcd(b, a % b);
}
 
// 최소공배수 : Least Common mulitple
int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

 

 

이제 반복문과 재귀 방식으로 나눠서 문제풀이를 진행해보도록 하겠습니다.

 

 

Case 1. 반복문

import java.util.*;
public class Main {
	public int gcd(int a, int b) {
		while (b != 0) {
			int r = a % b; // 나머지
 
			// GCD(a, b) = GCD(b, r)
			a = b;
			b = r;
		}
		return a;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int a = kb.nextInt();
		int b = kb.nextInt();
 
		int d = T.gcd(a, b);	// 최대공약수
 
		System.out.println(d); // 최대공약수
		System.out.println(a * b / d); // 최소공배수
	}
		

}

 

Case 2.  재귀

import java.util.*;
public class Main {
	public int gcd(int a, int b) {
		if (b == 0)
			return a;
            
		// GCD(a, b) = GCD(b, r), (r = a % b)
		return gcd(b, a % b);
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int a = kb.nextInt();
		int b = kb.nextInt();
 
		int d = T.gcd(a, b);	// 최대공약수
 
		System.out.println(d); // 최대공약수
		System.out.println(a * b / d); // 최소공배수
	}
		

}

 

---

 

물론 우리가 초등학교 때 배웠던 개념으로도 충분히 구현이 가능합니다. 

하지만 알고리즘 문제를 푸는 중간에 최대공약수, 최소공배수를 빠르게 구해서 다음 step으로 넘어가야 하는 경우를 생각해본다면 제가 처음 도전했던 방식이 얼마나 비효율적인지 알 수 있습니다.

 

제가 알고리즘 문제를 풀다가 중간에 기본으로 돌아갔던 이유이기도 합니다. 지금 당장은 돌아가는 것처럼 느껴지지만

기본기가 탄탄 + 논리적 사고가 가능해진다면 코테뿐만 아니라 현업에서도 도움이 많이 될 거라고 생각하고 있습니다. 

 

 

 

유클리드 호제법 GCD(a, b) = GCD(b, r)

    반복문

    재귀

최대공약수

최소공배수