백준#2609 GCD알고리즘 (유클리드 호제법)

문제

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

입력

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

출력

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

---

일단 이 문제를 처음 본 후 나는 머야 쉽네 하고 엄청난 자신감으로 for문을 써내려갔고 기특하게도 ' 맞았습니다!! '라는 문구가 나를 반겨줬다. 아래는 내가 작성한 코드이다.

import java.io.*;
import java.util.Scanner;
public class NUM2609 {
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int big=0, max=0, min=0;
		if(a>=b)
			big=a;
		if(a<b)
			big=b;
		
		for(int i=1; i<=big;i++) {		//최대공약수 구하기
			for(int j=1; j*i<=big; j++) {
				if((a%(i*j)==0) && (b%(i*j)==0))
					max=i;			
			}
		}		
		min = a*b/max;			//최소공배수 구하기
		System.out.printf("%d\n%d",max,min);
	}
}

맞았다는 사실에 기분이 좋긴 했지만 코알못인 내가 봐도 이 코드는 완벽한 정답이 아니었다. 다른 사람들의 풀이는 어떨까하고 바로 구글링~. 그리고 역시나처럼 나를 반기는 낯선 코드와 알고리즘ㅎㅎ.. 이 문제는 나처럼 단순무식 for문이 아니라 GCD라는 알고리즘을 써야했던 것이었다. 굉장히 기본적인 알고리즘이라는데.. 뭐 지금이라도 알았으니 됐다치고 내꺼로 만들기 시작!!

---

GCD ( 유클리드 호제법 )

GCD란 Greatest Common Divisor. 즉, 공통된 최대 약수라는 뜻이다. GCD는 하나하나 소인수분해하는 것이 아닌 '유클리드 호제법'을 사용하여 최대공약수를 구하는 알고리즘이다. 

<1071 % 1029 == 42    ----   1029%42==21   ----   42%21==0 >  이와 같은 일련의 과정이 유클리드 호제법이다.

즉, 두 수 a,b가 주어지고  r=a%b라 할 때 (a,b)의 최대공약수가 (b,r)의 최대공약수와 같다는 말이다.

이 알고리즘을 통해 최소공배수 또한 구할 수 있다.

두 수 A와 B의 최대공약수 d가 존재한다 하자. A=ad, B=bd와 같이 표현 할 수 있으며, 이때 a와 b는 자연히 서로수가 된다.

최소공배수는 a*b*d. 즉 A*B/d 라는 식으로 아주 쉽게 구해진다. 코드는 아래와 같다.

import java.io.*;
import java.util.StringTokenizer;

public class NUM2609 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		//공백 입력을 위한 StringTokenizer();
        
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int r=0;

		r = gcd(a,b);
		System.out.printf("%d\n%d",r,a*b/r);
	}

	//반복문을 사용한 GCD알고리즘
	public static int gcd(int a, int b) {
		while(b!=0) {
			int r=a%b;
			a=b;
			b=r;
		}
		return a;
	}
    
    /*
	 * 재귀를 사용한 GCD알고리즘
	public static int gcd(int a, int b) {
		if(b==0)
			return a;
	return gcd(b,a%b);
	}
	*/
}

---

Scanner보다  BufferedReader를 쓰는게 처리 속도가 훨씬 빠른거같다. 앞으로는 BufferedReader를 자주 사용하여 이 입력방법에 더 익숙해질 필요를 느꼈다. 

내가 알지 못하는 알고리즘이 몇백개는 더 되겠지만 열심히 하다보면 2개중 1개의 알고리즘을 보고  "나 이거 풀어본 적 있어! " 라는 말을 할 수 있게되지 않을까ㅎㅎ