[python] 백준 2609 : 최대공약수와 최소공배수

최대공약수를 구하는 방식엔 어떤게 있을까요? 보통은 주어진 정수를 소수의 곱으로 표현해 소수의 공통부분을 보겠지요. 

예를들어 100과 50의 최대공약수를 구할때 100=2^2x5^2, 50=2x5^2로 나타낸후 두 곱의 최대 공통부분인 2x5^2를 최대공약수로 결정합니다. 이게 우리가 초등학교때 배우는 방식이지요. 

그런데 만약 최대공약수를 구하는 코드를짤때도 위와같은 알고리즘이 효율적일까요? 위의 알고리즘을 사용하려면 일단 '소수'를 정의해줘야합니다. 소수를 정의해준후 입력받은 정수를 소수의 곱으로 나타내야하는데 이때 소수의 최솟값부터 검사를 해줘야겠죠. 이 과정을거쳐 두 정수가 소수의 곱으로 표현되었다면 이젠 곱의 공통영역을 구해주면됩니다.

근데 너무 비효율적인거 아닌가요? '소수'를 정의해주는 과정에서 이미 '약수'의 개념을 썼는데.. 

 

컴퓨터는 계산이 빠르죠. 인간이 봤을때 다소 노가다성 과정이더라도 컴퓨터입장에선 그저 쉬운 계산에 불과할수있습니다. 그냥 쉽게쉽게 생각해봅시다.

최대공약수의 후보에는 뭐가있을까요? 일단 두수의 최대공약수가 가질수있는 최댓값은 두수중 최솟값입니다. 입력받은 정수가 a,b일때 만약 a가 b의 약수라면 a가 두수의 최대공약수가 되는거죠. 위에서 예로든 100,50의 경우입니다. 이 두수의 최대공약수는 min(100,50)인 50입니다.

a가 b의 약수라면 최대공약수는 a, 약수가 아니라면 최대공약수는 a보다 작은 어떤 정수가되겠죠. 그렇다면 a부터 1씩 빼면서 순차적으로 검사해보는 방식은 어떨까요? for문을 쓰더라도 입력받는 정수가 10000이하이므로 충분히 시간안에 계산을 할수있겠네요.

a,b=map(int,input().split())

def gcd(a,b): 
    for i in range(min(a,b)):
        n=min(a,b)-i

        if a%n==0 and b%n==0:
            return n

gcd는 최대공약수의 영문 greatest common divisor의 약자입니다. 코드를 보면 입력받은 두 정수중 더 작은값에서부터 검사를 시작합니다. 공약수의 '최댓값'이므로 1부터 검사하는것보단, 최댓값에서 1씩 내려가는게 합리적이겠죠. 최대공약수 후보중 최댓값부터 1씩 빼면서 검사(a,b를 나눴을때 나머지가 0인지 아닌지)합니다. 만약 if문에 걸리면 n을 반환합니다.  i의 범위는 0~min(a,b)-1까지 이므로 if문에 만약 계속 안걸린다면 for문의 마지막에서 n=min(a,b)-(min(a,b)-1)=1입니다. 1은 무조건 if문에 걸리므로 1을 반환합니다. 

 

그럼 최소공배수도 비슷한 매커니즘으로 생각할수있지 않을까요? 최소공배수가 될수있는 후보값중 최솟값은? max(a,b)입니다. 100,50의 경우 최소공배수는 max(100,50)인 100이죠. 만약 100이 아니라면? 최소공배수처럼 1씩 더하면서 해볼까요? 만약 for문을 이용해 1씩 더한다면 그 끝을 지정해줄수 있을까요?

범위얘기가 나왔으니 한번 최소공배수의 후보값중 최댓값을 생각해봅시다.

최대공약수의 최솟값은 1, 최댓값은 min(a,b)입니다. 최소공배수의 최솟값은 max(a,b)이면 최댓값은 무엇일까요? 바로 a*b입니다. 두 수가 서로 공통된 소수곱 부분이 아예없다면 두수를 곱한값이 최소공배수가 되죠.

최댓값이 후보면 max(a,b)*min(a,b)이므로, max(a,b)부터 1씩 곱해가며 min(a,b)까지 for문을 돌리면 되겠네요.

def rcm(a,b):#최소공배수
    for i in range(1,min(a,b)+1)
        k=max(a,b)*i

        if k%a==0 and k%b==0:
            return k

 rcm은 최소공배수의 영문 least common multiple의 약자입니다. 최대공약수를 구할땐 min에서 1씩 빼며 검사했다면

최소공배수는 '배수'이므로 max에서 1씩 '곱하며' 검사합니다. for문의 범위가 min(a,b)+1까지인 이유는 min(a,b)까지가 최소공배수 계산에 포함되기 때문입니다. 최대공약수와 비슷한 매커니즘이지만 for문의 계산범위를 고려해 계산방식을 조금 변형하면 됩니다.

a,b=map(int,input().split())

def gcd(a,b): 
    for i in range(min(a,b)):
        n=min(a,b)-i

        if a%n==0 and b%n==0:
            return n
        
def rcm(a,b):
    for i in range(1,min(a,b)+1)
        k=max(a,b)*i

        if k%a==0 and k%b==0:
            return k

print(gcd(a,b))
print(rcm(a,b))

전체 코드입니다. 

학교에서 배웠던 지식으로 소수의 곱으로 나열해 계산하려하면 오히려 복잡해지는 문제입니다. 컴퓨터의 계산능력을 믿고 그냥 값의 범위를 생각해 코드를짜면 훨씬 깔끔해지죠?