[TIL] 2024-12-13_GCD/LCM

📕 Today I Learned - 오늘 내가 공부한 것을 정리합니다.

1. GCD(Greatest Common Divisor)

• 최대공약수는 두 수의 공통 약수 중 최댓값을 말한다.
  (약수는 나누어서 0이 되는 수를 말한다.)
• 이렇게 나누어서 0이 되는 수 중 공통적으로 들어가 있으며 그 중 최대값이 최대공약수이다.
• 자바에서는 BigInteger 클래스에 최대 공약수를 구할 수 있는 gcd() 함수를 제공한다.

1) BigInteger 클래스

import java.math.BigInteger;

public class Gcd {
    public static void main(String[] args) {
        System.out.println(gcd(48, 32));
    }

    private static int gcd(int a, int b) {
        BigInteger bigA = BigInteger.valueOf(a);
        BigInteger bigB = BigInteger.valueOf(b);
        BigInteger gcd = bigA.gcd(bigB);
        return gcd.intValue();
    }
}

2) 직접 구현: 유클리드 호제법

1. 큰 수(num1) 에서 작은 수(num2)를 나눈다.
2. 나머지(num1 % num2)가 0이 아니라면 나머지와 작은 수(num2)로 1번부터 다시 시작
3. [재귀호출] 1~2의 과정을 반복해서 나머지가 0 이라면 그 수가 최대공약수

public static int getGcd(int p, int q) {
        if (q == 0) return p;
        else return getGcd(q, p % q);
}

2. LCM(Least Common Multiple)

최소공배수란 두 수에서 서로 공통으로 존재하는 배수 중 가장 작은 수를 가리킨다.
최소공배수의 경우 두 수를 곱하고 그 값에 최대공약수를 나눈 값으로 구할 수 있다.

1) BigInteger 클래스

import java.math.BigInteger;

public class Lcm {
    public static void main(String[] args) {
        System.out.println(lcm(48, 32));
    }

    public static int lcm(int a, int b) {
        BigInteger bigA = BigInteger.valueOf(a);
        BigInteger bigB = BigInteger.valueOf(b);
        BigInteger lcm = (bigA.multiply(bigB)).divide(bigA.gcd(bigB));
        return lcm.intValue();
    }
}

2) 직접 구현: 최대공약수 사용

public static int getGcd(int p, int q) {
    if (q == 0) return p;
    else return getGcd(q, p % q);
}
    
public static int getLcm(int p, int q) {
    return (p * q) / getGcd(p, q);
}

---

💭 알고리즘 문제에서 최대공약수와 최소공배수 개념이 나와 다시 한번 정리해 보았다. 공부 해야할게 너무 많지만 조급해하지 말고 성실하게 즐겨보자 😎