최대공약수, 최소공배수 찾기 : 유클리드 호제법

최대공약수를 찾아야 하는 알고리즘 문제를 만났다 

2부터 하나 하나 나눠보다간 시간초과 나올게 뻔했다

그렇다면 몰러요ㅠ

검색해보니 최대공약수를 구하는 알고리즘이 존재했다 

이름도 멋져 유클리드 호제법

호제법은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘이다

유클리드씨께 최대공약수 찾는 비법 전수 받겠습니다

 

최대공약수(GCD) 구하기 : 유클리드 알고리즘

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

나머지가 0이 될 때까지 mod 연산을 반복하도록 구현하면 된다

O(logN)의 시간복잡도를 갖는다

 

반복문 구현

    fun gcd(num1: Int, num2: Int): Int {
        var (n1, n2) = if (num1 > num2) {
            Pair(num1, num2)
        } else {
            Pair(num2, num1)
        }
        
        while(n2 != 0) {
            val tmp = n1 % n2
            n1 = n2
            n2 = tmp
        }
        
        return n1
    }

재귀 구현

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

최소공배수 구하기(LCM)

두 수 a,b의 곱을 a,b의 최대공약수로 나누면 a,b의 최소공배수와 같다 

lcm = a*b / gcd

유클리드 호제법으로 최대공약수를 구한다면 최소공배수까지 알 수 있다

 

참고

https://nuritech.tistory.com/46

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

 

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var answer = IntArray(2)
        answer[0] = gcd(n, m)
        answer[1] = lcm(n, m, answer[0])
        return answer
    }
    
    // 최대공약수
    fun gcd(n1: Int, n2: Int): Int{
        return if (n2 == 0) n1
        else gcd(n2, n1 % n2)
    }
    
    // 최소공배수
    fun lcm(n1: Int, n2: Int, gcd: Int): Int {
        return (n1 * n2) / gcd
    }
}