ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [level1] - 최대공약수와 최소공배수(유클리드 호제법)
    programmers/level1 2020. 7. 24. 00:06

     

     

     

    코딩테스트 연습 - 최대공약수와 최소공배수

    두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의

    programmers.co.kr

     

    문제 설명 :

    두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

     

    입출력 예 :

    n m return
    3 12 [3, 12]
    2 5 [1, 10]


    접근 방법 :

    이 문제를 풀기 전에 먼저 최대공약수최소공배수를 알아야 한다.

    최대공약수란?

    두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

    예를 들어, 5와 10의 약수는 각각

    ex) 5는 1, 5

    ex) 10은 1, 2, 5, 10

    즉, 약수 중 공통인 수 가운데 가장 최대인 수는 5이므로 최대 공약수는 5라 할 수 있다. 

     

    최소공배수란?

    예를 들어 또 5와 10이 있고, 각각의 배수는

    ex) 5는 5, 10, 15, 20, 25...

    ex) 10은 10, 20, 30, 40, 50...

    즉, 공통인 배수들 중에 가장 최소인 수는 10이므로 최소 공배수는 10이라 할 수 있다.

     필자는 우선 최대공약수를 구하기 위해 유클리드 호제법을 활용해서 구해 볼 것이다.

    유클리드 호제법이란?

    두 수가 서로 상대방 수를 나눠서 결국 원하는 수를 얻는 알고리즘을 말하며, 유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다.

    즉, 두 수 A와 B가 있으면 서로의 수를 나누어가기를 반복하며 나머지가 0이 되었을 때의 나누는 수가 A와 B의 최대공약수이다.

    예를 들어, 2개의 자연수 58과 18가 있다. (단, a > b)

    No.

    GCD(A, B)

    A

    B

    A%B

    1

    GCD(58,18) 

    58 

    18 

    2

    GCD(18,4) 

    18 

    3

    GCD(4,2) 

    해당 순서대로 두 수를 계속 나누고 나머지가 0이 되는 순간 B의 수가 최대공약수가 된다.

    최대공약수 구하는 방식을 코드로 나타내면, 밑에 처럼 나머지가 0이 될 때까지 재귀 함수를 이용한 로직이 나온다.

    function solution(n, m) {
        const GCD = getGCD(Math.max(n, m),Math.min(n,m));
        return GCD;
    }
    const getGCD = (n, m) => {
        return m === 0 ? n : getGCD(m, n % m);
    }
    

     

    그다음 최소공배수를 구하는 것은 어렵지 않다.

    최소공배수(LMC) = 두 수의 곱한 값 / 최대공약수(GCD)

    두 수를 곱한 값과, 두 수의 최대공약수를 나누면 최소공배수가 나온다.

    최대공약수와 최소공배수를 구했기 때문에, 이제 배열에 순서대로 push()해서 순서대로 추가하고 반환하면 된다.

    이를 통해 최종적으로 다음과 같은 로직을 짜보았다.

     

    내가 짠 코드 :

    function solution(n, m) {
        let ansewer = [];
        const GCD = getGCD(Math.max(n, m),Math.min(n,m));
        ansewer.push(GCD);
        const LCM = getLCM(n * m ,GCD);
        ansewer.push(LCM);
        return ansewer;
    }
    const getGCD = (n, m) => {
        return m === 0 ? n : getGCD(m, n % m);
    }
    
    const getLCM = (a, b) => {
        return a / b;
    }

     

    'programmers > level1' 카테고리의 다른 글

    [level1] - 같은 숫자는 싫어  (0) 2020.07.27
    [level1] - 약수의 합  (0) 2020.07.25
    [level1] - 평균 구하기  (0) 2020.07.21
    [level1] - 짝수와 홀수  (0) 2020.07.20
    [level1] - x만큼 간격이 있는 n개의 숫자도움말  (0) 2020.07.19

    댓글

Designed by Tistory.