(알고리즘) 최소공배수와 최대공약수 구하기

알고리즘 문제를 풀다 보면 최대 공약수와 최소 공배수를 활용한 문제들이 자주 등장한다

 

오늘은 N개의 최소공배수 문제를 통해서 최소 공배수와 최대 공약수의 연관 관계를 알아보려고 한다

 

해당 문제는 배열 내부의 값들의 최소 공배수를 반환 하는 문제이다 이 문제는 쉽게 말하면 최대 공약수를 구한 다음에 남은 값들을 곱하면 되는 문제이다

 

최대 공약수는 말 그대로 에서 공통된 약수들의 최대 값이다 즉 저 숫자들로 더 이상 나누어 떨어질 수 없는 상태 까지 나누고 나눈 값을 곱한 값이 최대 공약수 이다

 

최소 공배수는 말 그대로 저 숫자들의 공통된 최소 공배수로 이는 즉 최소 공약수를 구한 후에 나머지 값 까지 구한 값이 될 수 있다

 

즉 위의 예제의 경우에는 2가 최대 공약수, 168이 최소 공배수가 되는 것이다

 

그러면 코드로는 어떻게 구할까??

 

사실 코드로는 저렇게 한꺼번에 4개를 다 구할 수 없다

 

그러면??

 

반복문을 써서 하나 하나마다 최소 공배수를 구해준 다음에 그 값을 계속해서 곱해 나가는 것이다

 

fun getGreatestCommonDivisor(a: Int, b: Int): Int {
    var newA = a
    var newB = b
    var c: Int

    while (newB != 0) { // b 가 0 (소수) 가 아닐 때 까지 반복문을 돌린다
        c = newA % newB // 나누어 떨어지는 값을 구한다
        newA = newB
        newB = c
    }

    return newA // 해당 값이 a와 b의 최대 공약수가 된다
}

위 함수는 유클리드 호제법으로 2개의 수의 최대 공약수를 구하는 공식이다 이걸 활용하면 우리는 최소 공배수를 구할 수 있다

 

최소공배수는 위에 처럼 구할 수도 있지만 다르게 생각해보면 원래의 수를 곱하고 이것을 최대 공약수로 나누는 방법을 생각 해볼 수 있다

 

예를 들어 2 와 6이 있을 경우 2와 6을 곱하면 12가 되는데 이를 두 수의 최대공약수인 2로 나누어주면 6이 된다

 

이를 코드로 반환하면

(a * b) / getGreatestCommonDivisor(a, b)

 

이런 식의 코드로 최소 공배수를 구할 수 있다

 

그러면 이것을 활용해서 위의 문제를 풀어보면 다음과 같다

 

fun solution(arr: IntArray): Int {

    val newArr: LinkedList<Int> = LinkedList()

    for(i in arr){
        newArr.add(i)
    }
    var c: Int = newArr.pop()
    while(!newArr.isEmpty()){
        val d = newArr.pop()
        val result = c * d

        c = result / getGreatestCommonDivisor(c, d)
    }


    return c
}

fun getGreatestCommonDivisor(a: Int, b: Int): Int {
    var newA = a
    var newB = b
    var c: Int

    while (newB != 0) {
        c = newA % newB
        newA = newB
        newB = c
    }

    return newA
}

 

문제 특성상 List에서 값을 빼내기 위해서 LinkedList를 사용했다 

 

해당 리스트에서 빼낸 값 2개의 최소 공배수를 계속해서 구하는 식으로 코드를 완성했다