Lv1. 최대공약수와 최소공배수

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

1. 풀이 설명

유클리드 호제법을 사용하여 최대공약수를 구하고
최대공약수를 이용하여 최소공배수를 구하여 반환한다.

2. 나의 풀이

def solution(n, m):
    answer = []
    answer.append(gcd(n, m))
    answer.append(n * m // gcd(n, m))
    return answer

def gcd(n, m):
    if n%m == 0:
        return m
    return gcd(m, n%m)

fun solution(n: Int, m: Int): IntArray
	= intArrayOf(gcd(n, m), (n / gcd(n, m)) * m)
    
fun gcd(a: Int, b: Int): Int {
	if (a%b == 0) return b
    return gcd(b, a%b)
}

3. 배운점

1. 최대공약수는 유클리드호제법으로 푼다.

GCD(a, b) == GCD(b, a%b)
if a%b == 0:
    b
else:
    GCD(b, a%b)

2. a와 b의 최대공배수 = a * b / GCD(a,b)

3. a<b 일 때, a%b==a

4. python에서 / 는 float // 는 int 로 결과를 반환한다.