[Algorithm] 최대공약수 구하기 - 유클리드 호제법 (Euclidean algorithm)

유클리드 호제법이란? (이름이 뭔가 굉장해서 처음 들으면 쫄게 된다 😇)

사실 간단하다. 그냥 2개 자연수의 최대공약수를 구하는 알고리즘이다. 

유클리드 호제법(Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 《원론》 제7권, 명제 1부터 3까지에 해당한다.
- 위키백과

 

Euclidean algorithm 원리

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

위 원리에 따라 최대공약수를 구하는 과정은 아래와 같다.

 

a 를 b 로 나눈 나머지를 r 이라 하자.

• r 이 0일 경우: 최대공약수는 b 
• r 이 0이 아닐 경우 
  • b 를 r 로 나눈 나머지를 l 이라 하자.
    • l 이 0일 경우: 최대공약수는 r
    • l 이 0이 아닐 경우: 나머지가 0이 나올 때까지 반복~

 

예시 1.

28과 21의 최대공약수를 구해보자.

• 28 을 21로 나누면? 👉 나머지가 7
• 21을 7로 나누면? 👉 나머지 0 👉 최대공약수는 7 !!!!!

 

예시 2.

28과 14의 최대공약수를 구해보자.

• 28 을 14로 나누면? 👉 나머지가 0 👉 최대공약수는 14 !!!

 

 

Kotlin으로 알고리즘을 구현해보자

2가지 방법으로 구현해볼 수 있다.

1. while loop 사용
2. 재귀 법(recursion) 사용

 

참고: 최대공약수를 영어로 Greatest Common Divisor 또는 Highest Common Fractor 라고 해서 최대공약수를 구하는 함수명을 보통 gcd() 라고 한다. 

 

1️⃣ while loop 사용

// 최대공약수 구하기 (유클리드 알고리즘)
// Greatest Common Divisor
fun gcd(a: Int, b: Int): Int {
    var num1 = a
    var num2 = b

    var remainder = num1 % num2
    while (remainder != 0) {
        num1 = num2
        num2 = remainder

        remainder = num1 % num2
    }

    return num2
}

 

2️⃣ 재귀 법 사용

확실히 재귀 함수를 사용하니 코드는 엄청 짧다 

fun gcdByRecursion(a: Int, b: Int): Int {
    val remainder = a % b
    if (remainder == 0) return b

    return gcdByRecursion(b, remainder)
}

---

 

(Extra)

추가로, while 루프를 사용했을 때와 재귀 법을 사용했을 때 어느 방법이 더 빠른지를 비교해봤는데,, 

결론은 큰 차이가 없는 것 같다. (다양한 케이스로 정밀하게 테스트해본 것이 아니기 때문에 그런 것 같다는 점~ 그냥 가볍게 확인해본 정도) 

아래 코드를 보면, while 루프의 경우 1223 ns, 재귀의 경우 2752 ns 로 큰 차이가 없다. 또한, a/b 값을 작게 했을 때는 while 루프의 경우가 조금 더 오래 걸렸는데 사실 다양한 케이스를 해본 게 아니기도 하고, 시간차가 정말 작기 때문에 위와 같은 결론을 내림. 

val a = 7890123456234989088
val b = 123456238394739892
// 나노 타임으로 측정한 것 
val timeFromGcd = measureNanoTime {
    gcd(a, b)
}
val timeFromGcdRecursion = measureNanoTime {
    gcdByRecursion(a, b)
}
println("timeFromGcd: $timeFromGcd, timeFromGcdRecursion: $timeFromGcdRecursion")
// 출력: timeFromGcd: 1223, timeFromGcdRecursion: 2752