[Argorithm]유클리드 호제법(GCD), LCM

📝 유클리드 호제법(GCD)

유클리드 호제법이란? 사실 어렵게 보이지만
최대공약수를 구하는 것에 사용되는 것을 말한다.

📌 약수 

• 어떤 수를 나누어떨어지게 하는 수
  • 나머지가 0이되는 것을 말함

N의 약수의 개수를 구하는 방법

• 1부터 N이하의 정수를 n으로 나누어서, 나머지가 0이 되는 수의 개수를 찾는다.
  • 시간 복잡도 : O(N)
• 1부터 루트 N 이하의 정수로 N을 나누어서, 나머지가 0이 되는 수의 개수를 찾고, 그 개수에 2를 곱함 N이 제곱수이면, 그 수에 1을 뺌
  • 시간복잡도 ; O(루트N)
  • 제곱수 : 어떠한 정수의 제곱이 되는 정수 

 

📌 유클리드 호제법이란?

• 호제법이란 말은 두 수가 서로 상대방 수를 나누어 원하는 수를 구하는 것을 의미한다.
• 수학적 성질
  • 두 자연수 A, B에 대해서(A > B) A를 B로 나눈 나머지가 R이라면, A와 B의 최대공약수는 B와 R의 최대공약수와 동일하다.
  • 이 성질에 따라, B를 R로 나눈 나머지 R1을 구하고, 다시 R을 R1으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 A와 B의 최대공약수이다. 

📝 실습

1071과 1029의 최대 공약수를 구해보자

• 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 계산한다.
  • 42
• 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 계산한다.
  • 21
• 42는 21로 나누어 떨어지므로, 1071과 1029의 최대공약수는 21이다.

public static int GCD(int a, int b){
	while(b!=0){
    	int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

 

📝 LCM

최대공약수를 구해보았으니 최소 공배수를 구해보자 

📌 배수

• 어떤 수를 곱한 수를 의미한다.
• 공배수는 두 수의 배수 중에서 일치하는 것을 말한다.

📌 수학적 원리

어떠한 두 수의 곱은, 그 두 수의 최대공약수와 최소공배수의 곱과 같다.

 

public static int LCM(int a, int b){
	int gcd = GCD(a,b);
    retunr (a * b) / gcd;
}

 

📝 백준 5347번 LCM

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        for(int i = 0; i < n; i++){
            String line = br.readLine().trim();
            StringTokenizer st = new StringTokenizer(line);
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            System.out.println(LCM(a, b));
        }
    }

    public static int GCD(int a, int b){
        while(b != 0){
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static long LCM(int a, int b){
        int gcd = GCD(a, b);
        return (long) a * (long) b / gcd;
    }
}