[프로그래머스] 최대공약수와 최소공배수

문제

 

 

말그대로 최대공약수와 최소공배수를 구하는 문제다. 처음에는 반복문으로 구해야하나 하다가 좀더 단순하고 간결하게 구하는 방법이 없을까 구글링하다 유클리드 호제법이라는 최대공약수를 구하는 방법을 알게 되었다. 최대공약수를 구하면 최소공배수도 자연스럽게 구할 수 있으니까 먼저 최대공약수를 구하기로 했다.

---

 

나의 풀이

function solution(n, m) {
    function gcd(a, b) {
  
      if (b === 0 ){
          return a
      }
          return gcd(b,a%b)
     }
    let GCD = gcd(n,m)
    let LCM = (n*m)/ GCD
    let answer =[GCD, LCM]
    
    return answer
}

 

유클리드 호제법을 통해서 최대공약수를 구하고(GCD) n,m을 곱한 값에 최대공약수를 나누면 최소공배수가 나온다.

두 수 A와 B의 최대공약수는 B와 A를 B로 나눈 나머지의 최대공약수와 동일하다는 원리를 기반으로 한다.

즉, GCD(A, B) = GCD(B, A % B)

 

 

호제법: 두 수가 서로 상대방의 수를 나누어서 결국 원하는 수를 얻는 알고리즘

 

위의 표를 보면 이해가 쉽다. 

 

1. 큰 수를 작은 수로 나눈 나머지를 구한다. (72 % 30)
2. 나누었던 수(B)와 그 나머지(A % B의 결과인 12)로 다시 나머지 연산을 한다.
3. 이 과정을 나머지(A % B)가 0이 될 때까지 반복하며, 0이 된 시점에서의 첫 피연산자(B=6)가 최대 공약수가 된다.

A % B가 0이 되는 순간 B의 값이 최대 공약수 가 된다.

 

이 방법을 사용하면 n.m의 숫자크기에 상관없이 계산할 수 있다.

---

다른 사람 풀이

 

 

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

 

같은 유클리드 호제법으로 푼 문제다. 더 직관적이고 간결하다. 마지막 증감문 부분이 처음에 조금 이해가 잘 안갔지만 결국 내가 쓴 풀이와 같다는 걸 알게됨

---

회고

 

유클리드 호제법에 대해 알게 되었다. 좋은 코드란 간결할 뿐만 아니라 더 직관적으로 알아보기 쉬운 코드여야할 것 같다.