[python] 백준 2609번 최대공약수와 최소공배수 문제 풀이

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

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

 

 

 

문제

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

 

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000 이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

 

 

 

---

 

💻 코드

 

 

방법 1) 단순 수식

 

 

num1, num2 = map(int, input().split())

def GCD(x, y):
    for i in range(1, min(x, y) + 1):
        if ((x % i == 0) and (y % i == 0)):
            result = i

    return result

def LCM(x, y):
    return x * y // GCD(x, y)

print(GCD(num1, num2))
print(LCM(num1, num2))

 

 

 

 

방법 2) 유클리드 호제법 사용

 

 

num1, num2 = map(int, input().split())

def GCD(x, y):
    while y > 0:
        x, y = y, x % y

    return x

def LCM(x, y):
    return x * y // GCD(x, y)

print(GCD(num1, num2))
print(LCM(num1, num2))

 

 

 

 

방법 3) 내장되어있는 함수 사용

 

 

import math

num1, num2 = map(int, input().split())

print(math.gcd(num1, num2))
print(math.lcm(num1, num2))

 

 

---

 

📝 풀이

 

 

최대공약수 : 0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수

최소공배수 : 2개 이상의 수의 공배수 가운데서 최소인 수

 

 

최대공약수와 최소공배수를 구하는 방법은 다양한 방법이 있다. 그 중 3가지 방법을 사용하여 풀어보았다.

 

 

 

 

방법 1) 은 가장 일반적인 방법이다.

최대공약수가 공통되는 약수 중 가장 큰 수라는 것이므로 일단 for문을 이용하여 i를 1부터 두 수 중 작은 수까지 두 수를 각각 i로 나눈 나머지가 모두 0인 수, 즉 공약수를 구한다. 그다음 이것을 계속 반복하면서 result라는 변수에 넣게 되면 마지막에는 이 변수에 공약수 중 가장 큰 값이 저장되게 되므로 최대공약수를 구할 수 있게 된다.

 

 

 

방법 2) 는 유클리드 호제법을 사용한 풀이이다.

 

 

먼저 유클리드 호제법에 대해 알아보자.

 

 

유클리드 호제법이란?

주어진 두 정수의 최대공약수를 구하기 위해 두 수 중에서 큰 수를 상대방(호, 互)의 수로 나누는(제, 除) 일을 최종적으로 나머지가 0이 될 때까지 반복하여 최대공약수를 얻을 수 있는 알고리즘

 

 

간단하게 말하면 두 수 중에서 큰 수를 작은 수로 반복해서 나누어 나머지가 0이 될 때까지 반복하여 최대공약수를 구하는 방법이다.

 

 

 

예시를 통해 알아보자.

 

두 수 24와 18의 최대공약수를 구하려고 한다. 먼저 두 수 중 큰 수 24를 작은 수 18로 나눈 나머지를 구한다. 24 % 18 = 6이 나온다. (이때 =은 등식의 의미이다.) 나머지가 0이 아니므로 다시 큰 수 18을 작은 수 6으로 나눈 나머지를 구한다. 18 % 6 = 0이 나온다. 나머지가 0이 나왔으므로 최대공약수는 6이 된다.

 

24 % 18 = 6

18 % 6 = 0

 

∵ 최대공약수 : 6

 

 

 

 

이것을 코드로 표현하면 다음과 같다.

 

def GCD(x, y):
    while y > 0:
        x, y = y, x % y

    return x

 

 

x, y = y, x % y 라는 코드는 파이썬에서만 사용할 수 있는 여러 값을 동시 대입하면서 swap 하는 코드이다. x에 y를 대입하면서 동시에 y에는 x % y를 대입한다. y에 x % y를 대입하는 과정에서 x는 y를 대입하기 전의 x를 넣는 것이다. 따라서 x = y; y = x % y와는 다른 코드이다.

 

 

 

 

방법 3) 은 math라는 라이브러리에 이미 내장되어있는 함수를 사용하는 것이다. 

 

math를 import한 후에 함수 사용할 때 math.gcd(숫자 1, 숫자 2), math.lcm(숫자 1, 숫자 2)와 같이 작성하면 최대공약수와 최소공배수를 매우 간단하게 구할 수 있다.