알골 3번(Python) - 최소공배수, 최대공약수 구하기 (백준 2609번)

출처

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

---

전체 코드

def euclid(num1, num2):
    tmp = num1%num2
    if tmp == 0:
        return num2
    else:
        return euclid(num2, tmp)
        

inputNum = list(map(int,input().split()))
inputNum.sort

minNum = euclid(inputNum[0], inputNum[1])
maxNum = (inputNum[0] * inputNum[1]) // minNum

print(minNum)
print(maxNum)

 

알고리즘 설명(유클리드 호제법)

최대공약수를 구하는 방법 중 하나인 유클리드 호제법을 사용하여 문제를 해결하였다.

 

유클리드 호제법

 

최대공약수를 구하려고 하는 두 수를 A와 B라고 치자.(A > B)

두 개의 자연수(또는 정식) A, B에서 A를 B로 나눈 나머지를 R이라고 한다면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. 이 성질에 따라 B를 R로 나눈 나머지 R'을 구하고, 다시 R을 R'으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 A와 B의 최대공약수이다.

출처 : 위키백과 유클리드 호제법 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

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

이 알고리즘을 재귀함수로 구현하였다. 

def euclid(num1, num2):
    tmp = num1%num2
    if tmp == 0:
        return num2
    else:
        return euclid(num2, tmp)

 

tmp는 나머지를 저장하는 변수이다. num1에는 큰 값, num2에는 작은 값이 인자로 들어오고, num1을 num2로 나눈 나머지를 tmp에 저장한다. tmp가 0이되면 그때의 num2가 최대공약수이기 때문에 num2를 return한다. tmp가 0이 아니라면 num1 자리에 num2를 넣고, num2 자리에 tmp을 대입하여 다시 euclid 함수를 호출한다. 

 

최소공배수는 최소공배수를 구하려고 하는 두 수를 곱한 후 최대공약수로 나눈 값이다.

 

 

피드백은 언제나 환영입니다! 감사합니다!