유클리드 호제법이란?

코테에서 흔히 쓰이는 알고리즘 방법인가보다! 수학적인 증명이겠거니..외우려고 한다..

유클리드 호제법은 두 수의 최대 공약수를 구하는 효율적인 방법

 

private int gcd(int a, int b) {
    if (b == 0) return a; // b가 0이면 a가 최대공약수
    return gcd(b, a % b); // 재귀 호출로 계속 나머지를 계산
}

 

1. 유클리드 호제법의 원리

두 개의 자연수 a, b(a > b)에 대해,

• GCD(a, b) == GCD(b, a % b)가 성립
• 즉, a를 b로 나눈 나머지를 새로운 b로 삼고, 원래의 b를 새로운 a로 두고 다시 GCD를 구하는 과정을 반복하면 결국 최대공약수가 나오는 원리다!

이 과정을 b가 0이 될 때까지 반복하면 a가 최대공약수가 된다 !! 

 

2. 예제: GCD(48, 18) 구하기

1. 48 % 18 = 12
   → GCD(48, 18) == GCD(18, 12)
2. 18 % 12 = 6
   → GCD(18, 12) == GCD(12, 6)
3. 12 % 6 = 0
   → GCD(12, 6) == GCD(6, 0)
4. b가 0이므로 GCD는 6

 

** 최소공배수는 두 수의 곱을 최대공약수로 나눈 것 !