2020. 5. 4. 08:43

[python](프로그래머스)최대공약수와 최소공배수

문제 설명


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

 

제한 사항


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

 

문제 풀이


from math import gcd

def solution(n, m):
    return [gcd(n,m), n*m // gcd(n,m)]

최대공약수란 두 개 이상의 정수의 공통 약수 중에서 가장 큰 값을 의미한다. 위는 math 라이브러리를 이용한 최대공약수를 간단하게 구하는 방법이고 실제 최대 공약수를 알고리즘은 다음과 같이 작동된다.

 

최대공약수를 구하는 알고리즘


  1. 두 수 중에 작은 값을 임시 변수에 저장한다.
  2. 임시 변수로 두 수를 나누어 약수가 되는지 확인한다.
  3. 나눌 수 없다면 임시 변수에서 하나씩 빼가며 다시 확인한다.
  4. 공통된 약수라면 이 값을 결과로 리턴하고 종료한다.
def gcd(a,b):
    i = min(a,b)
    while True:
        if a % i == 0 and b % i == 0: #나머지가 0이라는 건 딱 떨어지는 약수라는 뜻!
            return i
        i-=1

이를 유클리드 호제법을 이용하면 간단하게 만들 수 있다.

 

유클리드 호제법


유클리드 호제법은 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는다는 뜻.

2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이를 식으로 표현하면

두 정수 a,b의 최대공약수를 G(a,b)라고 할 때, a,b,q r(b ≠ 0)에 대하여 a = bq +r이면 G(a,b) = G(b, r)가 성립한다.

  1. 최대공약수를 구하는 함수를 gcd(x,y)라고 가정
  2. x % y = 0이라면 gcd(x, y) = y가 성립
  3. x % y ≠ 0이라면 gcd(x, y) = y가 성립
  4. 2번이 될 때까지 2~3번을 반복

이를 코드로 바구면 아래와 같다.

def gcd(x, y):
		# y가 0이 될 때까지 반복
		while y:
				x, y = y, x % y
		return x

 

다른 풀이


def gcdlcm(a, b):
    c, d = max(a, b), min(a, b)
    t = 1
    while t > 0:
        t = c % d
        c, d = d, t
    answer = [c, int(a*b/c)]

    return answer

유클리드 호제법을 이용한 문제 풀이법이다. 최소공배수는 두 수를 곱한 값에 두수의 최대공약수를 나누어주면 된다.