유클리드 호제법을 이용하여 GCD를 구하는 방법

• [ ] 유클리드 알고리즘의 원리 ? → 두 수 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);
}

<aside> 💡

참고자료

https://thin-azimuth-2a9.notion.site/N-cf-62e59f1f8755417daad24294dc6fa036?pvs=4

</aside>

문제: 최대공약수 (백준 1850)

문제 링크

알고리즘 [접근 방법]

• [ ] 유클리드 알고리즘을 이용하여 최대공약수를 구하면 된다.