[알고리즘-JAVA] 백준 알고리즘 2609번 - 최대공약수와 최소공배수

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

두개 자연수의 최대공약수와 최소 공배수를 출력하는 문제이다.

2. 나의 방식대로 문제를 재정의 하자.

유클리드 알고리즘과, 최대공약수 최소공배수간의 관계를 이용해 구한다.

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

유클리드 알고리즘!

4. 어떻게 계산할 것인가?
1) 입력

BufferedReader, InputStreamReader를 이용

 

2) 시간 복잡도 계산

유클리드 알고리즘의 시간복잡도는 잘 모르겠다...

O(a%b)인것같다.

5. 주의할 점은 무엇인가?

.

 

6. 풀이 과정

 

최대공약수

* 최대공약수는 줄여서 GCD라고 쓴다.

* 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수.

* 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누기

===> 시간복잡도 : O(N)

* 최대 공약수가 1인 두 수를 서로소(Coprime)이라고 함.

 

유클리드 호제법 : 최대공약수 빠르게 구하는 방법

* R = A%B

* GCD(A,B) = GCD(B,R) 이용.

* a%b에서 a<b일경우 a%b = a이다.

(따라서 a와 b의 대소비교가 필요없다.)

// 재귀 알고리즘.
int gcd(int a, int b) {
	if ( b == 0 ) {
    	return a;
    } else {
    	return gcd(b, a%b);
    }
}

// 비재귀 알고리즘.
// 재귀 호출이 하나뿐일 경우 바꿀 수 있음.
int gcd(int a, int b) {
	while (b != 0) {
    	int r = a%b;
        a = b;
        b = r;
    }
}

세 수의 최대공약수 : GCD(GCD(a,b),c)로 구하면 된다.

 

최소공배수

* 최소공배수는 줄여서 LCM이라고 한다.

* 두 수의 최소 공배수는 두 수의 공통된 배수 중에서 가장 작은 정수

* 최소공배수는 GCD를 응용해서 구함.

* 두 수 a, b의 최대공약수를 g라고 하면,

* 최소공배수와 최대공약수의 곱은 두 수의 곱과 같다.

L = G * (A/G) * (B/G)

L * G = A * B

L = A * B / G

 

전체 소스 코드

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine()," ");
        int a = Integer.parseInt(stk.nextToken());
        int b = Integer.parseInt(stk.nextToken());
        int G = Uclid(a, b);
        long L = a*b/G;
        System.out.println(G);
        System.out.println(L);
    }

    public static int Uclid(int a, int b){
        if (b==0){
            return a;
        }
        else{
            return Uclid(b, a%b);
        }
    }
}