최초의 알고리즘 중 하나! 유클리드 호제법으로 최대공약수 구하기

유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법 중 하나로, 인류 최초의 알고리즘 중 하나로서도 알려져 있습니다.

두 수 a와 b의 최대공약수를 구하기 위해서는, 다음과 같은 과정을 반복합니다.

• a를 b로 나눈 나머지 r을 구합니다.
• 만약 r이 0이면, b가 a와 b의 최대공약수가 됩니다. 즉, GCD(a, b) = b입니다.
• 만약 r이 0이 아니라면, b와 r의 최대공약수를 구하기 위해, 다시 b를 r로 나눕니다. 이때, r이 0이 될 때까지 반복합니다.

fun gcd(a: Int, b: Int): Int {
    if (b == 0) return a
    return gcd(b, a % b)
}

예를 들어, 54와 24의 최대공약수를 구하려면 다음과 같이 할 수 있습니다.

 

1. 54를 24로 나누면 나머지는 6입니다. (54 = 2 x 24 + 6)
   1. 최초 시작시 큰수 작은 수의 순서는 상관이 없음
          24를 54로 나누면 24가 남고 다시 54가 24로 나누게 된다.
2. 24를 6으로 나누면 나머지는 0입니다. (24 = 4 x 6 + 0)
3. 따라서, 54와 24의 최대공약수는 6입니다.

또한, 유클리드 호제법은 최소공배수(LCM, Least Common Multiple)를 구하는데에도 활용될 수 있습니다.

LCM(a, b) = (a x b) / GCD(a, b)의 공식을 이용하여, 두 수의 최소공배수를 구할 수 있습니다.