[알고리즘] 유클리드 호제법 + [백준 2609번] (Kotlin)

유클리드 호제법이란?

2개의 자연수쌍의 최대공약수를 구하는 알고리즘입니다.

또한, 최대공약수를 이용하여 최소공배수를 구할 수 있습니다.

 

최대공약수 (GCD, Greatest Common Divisor)

2개의 자연수 a, b에 대해 a를 b로 나눈 나머지를 r이라 할 때, a와 b의 최대공약수는 a와 r의 최대공약수와 같습니다. 이 과정을 반복하여 나머지가 0이 되었을 때 나누었던 수가 a와 b의 최대공약수입니다.

 

☞ 예를 들어 (a= 24, b= 18)에 대해 최대공약수를 구해보겠습니다.

이때, r= a%b = 6이고 다시 b를 r(a%b)로 나누면 나머지가 0이 되어 최대공약수는 6이 됩니다.

최소공배수 (LCM, Least Common Multiple)

최소공배수는 위에서 구한 최대공약수를 활용해 구할 수 있습니다.

a와 b의 곱을 최대공약수로 나눈 값이 최소공배수가 됩니다.

 

☞ 예를 들어 위에서 24와 18의 경우 최대공약수가 6이고, a와 b의 곱은 432이기 때문에 432를 6으로 나눈 72가 최소공배수가 됩니다.

 

유클리드 호제법을 활용한 예제로 [백준 2609번 : 최대공약수와 최소공배수] 문제를 해결해 보겠습니다.

2609번: 최대공약수와 최소공배수

---

나의 풀이

fun main() {
    val (a, b) = readLine()!!.split(" ").map { it.toInt() }

    // 최대공약수
    val gcd = gcd(a, b)
    // 최소공배수
    val lcm = (a * b) / gcd

    println(gcd)
    println(lcm)
}

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