수학 알고리즘 예제(5). 백준 [2609] 최대공약수와 최소공배수

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

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

선형적인 탐색법으로 작은 수전까지 하나씩 나누어 보고 둘 다 나누어 떨어지는 수 중 가장 큰 수를 구하면 되겠지만, 
다른 수학적인 방법을 이용하여 최대공약수를 구한 뒤 그를 이용하여 최소 공배수까지 구하는 방법이 있다.

임의의 수 a, b가 있다 가정하자. (단, a > b) 
a를 b로 나누면 몫과 나머지가 있을 것이다. 그러면 그 나머지로 나누는 수 (b)를 또 나눈다.
이를 반복하다 나누는 수 (b)가 0이 되면 나누어지는 수 a를 return 한다. 

그림을 보면 x가 최대공약수라 할 때,
a = 8x
b = 3x
a% b = 2x이다. 우리는 x를 구해야 하기 때문에, 나머지가 0이 될 때, 즉 모든 수가 나누어 떨어질 때까지 계속해서 b를 나머지로 나눈다.
8x / 3x = 2....... 2x
3x / 2x = 1....... x
2x / x = 2....... 0  --> 이때 x를 구할 수 있다.

위와 같은 과정을 반복해야 하기 때문에, 재귀 함수를 사용해서 문제를 해결한다.

그리고 이렇게 최대공약수를 구했다면 최소공배수를 구하는 과정은 다음과 같다.
임의의 수 a, b를 곱한 뒤, 최대 공약수로 나누면 최소공배수를 구할 수 있다. 
그 이유는 최대공약수 x를 갖고 있는 두 수 a, b가 있다.
a = x * a1
b = x * b1이라고 나타낼 수 있다. 두 수를 곱하면 x^2 * a1 * b1이다.
그렇다면 저 수를 x로 한번 나누어 주면 x * a1 * b1 이 되고 이것이 최소 공배수이다.

 

다음은 Java로 작성한 코드이다.

import java.util.Scanner;

public class gcdLcm {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		
		System.out.println(gcd(a,b));
		System.out.println(lcm(a,b));
	}
	
	public static int gcd(int a, int b) {
		if(b == 0) {
			return a;
		}
		int temp =gcd(b,a%b);
		return temp;
	}
	
	public static int lcm(int a, int b) {
		int x = gcd(a,b);
		return (a*b)/x;
	}

}