최소공배수를 구하는 2가지 방법

1. 소인수 분해 이용

• [ ] **중복되는 소인수(ex: 2)**는 차수가 가장 큰 횟수만큼, 그리고 **나머지 소인수(서로소)**를 모두 곱해주면 그 값이 최소공배수가 된다.

$10 = 2 * 5$ $12 = 2^2 * 3$ $15 = 3 * 5$ → 10, 12, 15의 최소공배수 = $2^2 * 3 * 5 = 60$

2. 최대공약수(GCD) 이용 (+ 유클리드 알고리즘)

• [ ] 최대공약수(GCD)를 이용하여 최소공배수(LCM)을 찾는 수학적으로 증명된 공식이 있다.

두 수의 최소공배수를 최대공약수를 이용해서 구하는 공식이다. $lcm(a,b)=∣ab∣​/gcd(a,b)$

**세 수 이상의 최소공배수**는 다음과 같이 함수를 계속 취해주면 된다. $lcm(a,b,c)=lcm(lcm(a,b),c)≡∣abc∣​/gcd(gcd(a,b)/∣ab∣​,c)$

• [ ] 유클리드 알고리즘의 원리 ? → 두 수 a와 b가 있을 때, a와 b의 GCD는 b와 a를 b로 나눈 나머지의 GCD와 같다 !

GCD(a, b) = GCD(b, a % b) ex) **GCD(48, 18)**를 구하는 과정

(1)	48 ÷ 18 = 2 (나머지 12) → GCD(48, 18) = GCD(18, 12)
(2)	18 ÷ 12 = 1 (나머지 6) → GCD(18, 12) = GCD(12, 6)
(3)	12 ÷ 6 = 2 (나머지 0) → GCD(12, 6) = GCD(6, 0) = 6

유클리드 알고리즘의 단계

1. 큰 수(a)를 작은 수(b)로 나눈 나머지를 구한다.
2. 작은 수(b)와 나머지(a % b)를 가지고 다시 나눗셈을 반복한다.
3. 나머지가 0이 될 때까지 이 과정을 반복하며, 나머지가 0이 된 순간 a값이 최대공약수이다.

// 최대공약수(GCD)를 구하는 유클리드 알고리즘
public static int gcd(int a, int b) {
    // 나머지가 0일 때, b가 최대공약수
    if (b == 0) {
        return a;
    }
    // 재귀 호출: GCD(a, b) = GCD(b, a % b)
    return gcd(b, a % b);
}

알고리즘 문제: 구명보트

• [ ] 최소공배수를 구하는 공식을 활용하면 쉽게 해결할 수 있는 문제였다.