최대공약수, 최소공배수 구하기

SeoYng·2020년 6월 28일

Lv1 알고리즘 알고리즘 문제풀이

최대공약수 구하기

👀 깃헙 소스

유클리드 호제법

2개의 자연수에서 최대공약수를 구하는 알고리즘의 하나
호제법이란 말은 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘을 나타낸다.

a와 b의 최대공약수를 (a, b)라하면 다음이 (a, b) = (b, r)이 성립한다.

ex) 12와 8의 최대공약수는 4이다.
12 = 8x1 + 4
8 = 4x2 +0
(12, 8) = (8, 4) = (4, 0) -> 4

코드

**(a>=b)

def gcd(a,b):
    return  a if b == 0 else gcd(b, a%b)

const gcd = (a, b) => b ? gcd(b, a%b) : a;

참고

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

최소공배수 구하기

최소공배수는 최대공약수를 알면 쉽게 구할 수 있다.
두 수를 곱한뒤 최대공약수로 나눠주면 된다.

ex) 12와 8의 최소공배수는 24이다. 이때 최대공약수는 4.
12 = 4x3
8 = 4x2
24 = 4x3x2 = 4x3x4x2//4

코드

**(a>=b)

def lcm(a,b):
    return  a * b // gcd(a, b)

const lcm = (a, b) =>  a * b / gcd(a, b)

프로그래머스 문제 - 최대공약수와 최소공배수 LV1

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

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

솔루션 - 위의 알고리즘을 적용하여 풀면된다. 소수와 마찬가지로 자주 등장하는 기본적이지만 알아둬야 하는 문제.

# 파이썬
def gcd(a, b): #최대공약수 구하기
    return a if b == 0 else gcd(b, a % b)

def solution(n, m):
    # a = max(n, m)
    # b = min(n, m)
    return [gcd(a, b), n*m // gcd(a, b)]

// 자바스크립트
function solution(n, m) {
    //const a = n > m ? n : m;
    //const b = n > m ? m : n;
    // 최대공약수 구하기
    const gcd = (a, b) => b ? gcd(b, a%b) : a;
    
    return [gcd(n,m), n*m / gcd(n,m)];
}