[Algorithm] 유클리드 호제법이란? (Kotlin)

유클리드는 수학자 이름으로 알고 있는데 호제법이란 단어 뜻이 뭔지 모르겠다. 네이버 사전에선 아래처럼 말한다.

 

두 정수 또는 두 정식인 a, b가 있을 때, a를 b로 나눈 나머지 a`로 b를 나누고 그 나머지로 a`를 나누는 일을 완전히 나눠질 때까지 계속해서 a와 b의 최대공약수를 구하는 방법. 단 a, b가 자연수일 때 a > b, 다항식일 때는 a의 차수가 b의 차수 이상이어야 한다

 

다른 건 둘째치고 일단 두 수의 최대공약수를 구하는 방법이란 건 알겠다. 참고로 최대공약수는 영어로 Gratest Common Divisor로 줄이면 GCD가 된다. 그래서 최대공약수 알고리즘 문제 해설을 보면 gcd라고 쓰는 건가 보다.

이제 이 포스팅의 제목인 유클리드 호제법이 뭔지 확인해본다. 위키백과에선 아래처럼 설명한다.

 

https://en.wikipedia.org/wiki/Euclidean_algorithm

Euclidean algorithm - Wikipedia

유클리드 알고리즘(호제법)은 두 정수의 최대공약수를 계산하는 효율적인 방법이다. 일반적으로 쓰이는 가장 오래된 알고리즘 중 하나다. 큰 수를 작은 수의 차이로 대체해도 두 수의 최대공약수는 안 변한다는 원리를 기반으로 한다. 예를 들어 21은 252와 105의 최대공약수고, 21은 105와 252에서 105를 뺀 147의 최대공약수기도 하다. 이 과정을 반복하면 두 숫자가 같아질 때까지 연속적으로 더 작은 숫자 쌍이 생성된다. 단계를 반대로 하거나 확장된 유클리드 알고리즘을 써서 최대공약수는 두 원래 숫자의 선형 조합으로 표현할 수 있다...(중략)

 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나눠서(除) 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b(단 a > b)에 대해서 a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r`를 구하고, 다시 r을 r`로 나눈 나머지를 구하는 과정을 반복해 나머지가 0이 됐을 때 나누는 수가 a, b의 최대공약수다...(중략)

 

108과 78의 최대공약수를 구한다고 치면 아래 과정을 통해 두 수의 최대공약수를 구할 수 있다.

 

• 108 % 78 = 30
• 78 % 30 = 18
• 30 % 18 = 12
• 18 % 12 = 6
• 12 % 6 = 0, 즉 6이 108과 78의 최대공약수

 

이것을 코틀린으로 구현한다면 아래와 같다.

 

fun main() {
    var a = 4
    var b = 10
    println("최대공약수 : ${gcd(a, b)}")
    println("최소공배수 : ${a * b / gcd(a, b)}")
}

tailrec fun gcd(a: Int, b:Int): Int = if (b != 0) gcd(b, a % b) else a

// 최대공약수 : 2
// 최소공배수 : 20

 

재귀호출을 통해서 구하는 방법이다. 이 때 gcd()가 스스로 자신만을 호출하다가 값을 리턴하기 때문에 꼬리재귀라고 할 수 있어서 tailrec을 붙였다.

tailrec은 꼬리재귀를 영어로 바꾼 Tail recursion의 일부 단어들을 가져온 형태의 키워드로, 해당 꼬리재귀 함수를 for 따위의 루프로 다시 작성할 수 있다고 컴파일러에 알려주는 키워드다. 그럼 컴파일러는 tailrec이 붙은 함수를 상대적으로 자원 소모가 적은 루프를 사용한 코드로 바꿔 컴파일한다. 스택오버플로우 에러가 발생하는 걸 방지해주는 것이다.

 

그리고 최소공배수도 구하는 걸 볼 수 있는데, 최소공배수는 두 수의 곱을 최대공약수로 나누면 구할 수 있어서 저렇게 쓰면 최소공배수도 같이 구할 수 있다.

 

 

참고한 사이트)

 

https://notepad96.tistory.com/92

Kotlin 최대공약수/최소공배수 - 유클리드 호제법