[Kotlin] 최대공약수와 최소공배수 (프로그래머스 알고리즘)

 

 

 

 

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12940

 

 

---

 

접근

 

구상, 실패코드

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        

    var answerset = IntArray(2)
    if(n < m){
        for (i in n downTo 1){
            if(m % i == 1 && n % i == 1) {
                answerset[0] = i 
                break}
             }        
    } 
        else{
        for (i in m downTo 1){
            if(m % i == 1 && n % i == 1){
                answerset[0] = i
                break}
              }
    }
    
    
    if(n < m){
        for (i in m..1000000){
            if(m % i == 1 && n % 1 == 1) {
                answerset[1] = i
                    break}
        } 
    }
        else{
            for (i in n..1000000){
            if(m % i == 1 && n % 1 == 1){
                answerset[1] = i
                break}
          }
          }
        return answerset
    }
}

• n과 m의 크기를 비교해서 상황에 따라 최소공약수와 최대공배수를 나누어 구하면 된다고 생각했다.
• 모든 return 값이 [0,0]으로 나와 실패했다.
• 이 코드에는 아래와 같은 문제가 있다.
• (1) 두 번째 반복문에서 n % 1을 확인하는 부분에서 1 대신에 i를 사용해야 한다.
  이 부분은 최소 공배수를 구하는 부분인데, n % 1은 항상 0이므로 이는 의미가 없다.
• (2) 두 번째 반복문에서 for (i in m..1000000)와 같이 1000000으로 하드코딩한 것은 좋지 않다.
  이 값을 더 효율적으로 관리해야 한다.
• (3) 최대공약수와 최소공배수를 혼동하고 있다.
  최대공약수는 n과 m의 공통된 약수 중 가장 큰 수를 의미하며, 최소공배수는 n과 m의 공통된 배수 중 가장 작은 수를 의미합니다. 현재 코드는 이 두 가지를 혼동하고 있다.
• (4)answerset 배열의 크기가 2로 고정되어 있으므로, 입력값이 조건을 벗어날 때 문제가 발생할 수 있다.

 

 

💡 유클리드 호제법이라는 게 있었다!

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

• 최대 공약수: gcd (greatest common diviser)
• 최소 공배수: lcm (least common multiple)

 

---

 

 

성공 코드

class Solution {
    fun solution(n: Int, m: Int): IntArray = intArrayOf(gcd(n, m), lcm(n, m))

    // 최대공약수
    fun gcd(n: Int, m: Int): Int {
        var num1 = n
        var num2 = m

        while (num2 != 0) {
            val r = num1 % num2
            num1 = num2
            num2 = r
        }

        return num1
    }

    // 최소공배수
    fun lcm(n: Int, m: Int): Int = n * m / gcd(n, m)
}

재귀함수를 이용한 풀이

class Solution {
    fun solution(n: Int, m: Int) = intArrayOf(gcd(n, m), lcm(n, m))
    
    fun lcm(n:Int, m:Int) = n * m / gcd(n, m)
    
    fun gcd(n:Int, m:Int):Int{
        return if(n < m){
            if(n == 0) m else gcd(n, m % n)
        }else{
            if(m == 0) n else gcd(m, n % m)
        }
    }
}

꼬리재귀를 이용한 풀이

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        val gcd = gcd(n, m)

        return intArrayOf(gcd, n * m / gcd)
    }

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

 

---

 

설명

 

1. 사실 유클리드 호제법의 방법에 대해서는 오랫동안 이해가 가지 않았다.
2. 유클리드 호제법에 의해 최대공약수를 구하는 내용은 아래와 같다.
   만약 b가 0이면, a가 최대 공약수이다. (a % 0 = a)
   그렇지 않으면, a를 b로 나눈 나머지를 구한다. (a % b)
   이때 나머지를 b로 대체하고, 이전의 b는 현재의 a로 대체한다. 즉, a와 b를 바꾼다.
   1번부터  이 과정을 다시 반복한다.
   이 과정을 반복하면, 마지막에 나머지가 0이 될 때까지 진행된다. 그때의 b가 최대 공약수가 된다.
   
   예를 들어, 48과 18의 최대 공약수를 구하는 과정은 아래와 같다.
   
   48 % 18 = 12
   18 % 12 = 6
   12 % 6 = 0
   나머지가 0이 되었으므로, 최대 공약수는 마지막에 남은 6이다.
3. 유클리드 호제법에 의하면 최소공배수는 '두 수의 곱'을 최대공약수로 나누면 나온다.
4. 유클리드 호제법에서는 두 수의 상대적 크기에 대한 고려가 필요하지 않다.
   이유는 최대 공약수를 찾는 과정에서 두 수를 반복적으로 나누기 때문이다.
   
   위에 정리된 내용과 같이 유클리드 호제법은 두 수의 최대 공약수를 구하는 과정에서 나눗셈 연산을 이용하여 수를 줄여나간다. 두 수 a와 b 중 어느 것이 더 큰지 비교하는 대신, 나머지 연산을 사용하여 계속해서 두 수의 크기를 비슷하게 만들어가는 것이 주요 아이디어이다.
   
   알고리즘이 동작하는 방식은 다음과 같다.
   
   만약 b가 0이라면, a가 최대 공약수이므로 이 시점에서 연산을 종료한다.
   그렇지 않으면, a를 b로 나눈 나머지를 구한다. 이 때 나머지는 항상 0보다 작거나 같고, a보다 작다.
   그리고 이전의 b는 현재의 a로, 이전의 나머지는 현재의 b로 대체하여 다시 나눗셈을 진행한다.
   이 과정을 반복하면, 항상 두 수는 점점 작아지고, 결국에는 하나의 수가 0이 되어 알고리즘이 종료된다. 이 시점에서 두 수 중 하나가 0이면, 다른 수가 최대 공약수가 되는 것이고, 이 수가 두 수의 최대 공약수이다.
5. 유클리드 호제법을 이용한 풀이는 재귀적이므로, tailrec(꼬리재귀)을 이용하여 간단하게 알고리즘을 짤 수 있다.

 

---

 

다른 방법

 

class Solution {
    fun solution(n: Int, m: Int): IntArray {
        var gcd = 1
        var lcm = n * m

        for(i in Math.min(n, m) downTo 1) {
            if(n % i == 0 && m % i == 0) {
                gcd = i
                break
            }
        }

        for(i in Math.max(n, m).. lcm) {
            if(i % n == 0 && i % m == 0) {
                lcm = i
                break
            }
        }
        var answer = intArrayOf(gcd, lcm)
        return answer
    }
}

• 내가 처음 접근했을 때 구상했던 방식으로 구현한 알고리즘이다.
• lcm을 n * m 으로 둔다는 점, if문의 조건이 == 0 이었다는 점에서 내 구상방법이 틀린 이유를 알 수 있었다.