코드

매우 직관적인 코딩

n, m = map(int, input().split())

ng_list = []
mg_list = []

nl_list = []
ml_list = []

def _GCD(n, m):
    for i in range(1, n + 1):
        if n % i == 0:
            ng_list.append(i)
            
    for i in range(1, m + 1):
        if m % i == 0:
            mg_list.append(i)
            
    GCD = [g for g in ng_list if g in mg_list]
      
    return GCD

def _LCM(n, m):
    for i in range(n, n * m+1, n):
        if i % n == 0:
            nl_list.append(i)
            
    for i in range(m, n * m+1, m):
        if i % m == 0:
            ml_list.append(i)
                 
    LCM = [l for l in nl_list if l in ml_list]
      
    return LCM

print(max(_GCD(n, m)))
print(min(_LCM(n, m)))     

n * m // 25

유클리드 호제법

n, m = map(int, input().split())

def _gcd(n, m):
    while m > 0:
        n, m = m, n % m
        
    return n

def _lcm(n, m):
    return  n * m // _gcd(n, m)

print(_gcd(n, m))
print(_lcm(n, m))

문제 해설

처음 코드를 짜고 정답을 맞췄으나 시간 복잡도 차원에서의 성능이 너무 좋지 않아 구글링을 통해 유클리드 호제법을 알게 되어 이를 토대로 코드를 다시 완성했다.

유클리드 호제법 참고

유클리드 호제법에 의하면 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 또한 a와 b를 곱한 값에 최대공약수를 나눠주면 그 값이 바로 최소공배수가 된다.

댓글남기기

참고