211224_Code in the morning

Code in the morning, 매일 아침 알고리즘 문제를 풉니다. 

💬 문제 설명 : 최대공약수와 최소공배수

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

 

 

📍 제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

 

 

💡 나의 풀이 

def solution(n, m):
    answer = []
    
    for i in range (min(n,m), 0, -1):
        if (n % i == 0) and (m % i == 0):
            answer.append(i)
            break
                        
    for j in range ( max(n,m), m*n+1 ):
        if (j % n ==0) and ( j%m ==0):
            answer.append(j)
            break
        
    return answer

 

💡 다른 해설

* 파이썬 최소공배수, 최대공약수를 구하는 내장함수로 쉽게 구할 수 있음

gcd(greatest common divisor) 

lcm(least common multiple) 

from math import gcd
def solution(n, m):
    gcd_num = gcd(n, m)
    lcm_num = n*m // gcd(n,m)
    answer = [gcd_num, lcm_num]
    return answer

 

 

 

유클리드 호제법

최대공약수를 찾을 때, 작은 수의 경우에는 사람이 직접 계산해서 찾을 수 있지만, 수가 무진장 커진다면 컴퓨터를 써야 합니다. 그런데 컴퓨터를 이용해 최대공약수를 찾을 때는, 위와 같이 소인수분해를 하기 보다는 유클리드 호제법이라는 알고리즘(문제를 풀기 위해 정해진 절차)를 사용하는 것이 더 빠릅니다. 유클리드 호제법은 다음 정리로부터 기인합니다.

 

AA를 BB로 나눈 몫을 QQ라 하고, 나머지를 RR이라 하자. 이 때, gcd(A,B)=gcd(B,R)gcd(A,B)=gcd(B,R)이다.

 

예시를 보겠습니다. 60를 24로 나눈 몫은 2이고 나머지는 12입니다. 즉, 60=24×2+1260=24×2+12입니다. 과연 gcd(60,24)=gcd(24,12)=12gcd(60,24)=gcd(24,12)=12임을 확인할 수 있습니다. 이 정리를 이용한 유클리드 호제법 알고리즘은 다음과 같습니다.

 

1. AA와 BB의 최대공약수를 구하기 위해서 AA를 BB로 나눈 나머지 R1R1을 구합니다.
2. BB를 R1R1으로 나눈 나머지 R2R2를 구합니다.
3. R1R1을 R2R2로 나눈 나머지 R3R3를 구합니다.
4. 이 과정을 계속 반복하여, 어느 한 쪽이 나누어떨어질 때까지 반복합니다. 이 직전 얻은 나머지가 최대공약수입니다.

 

👉🏻 문제 바로가기 

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

 

 

 

https://dimenchoi.tistory.com/46