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

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12940

개념 & 문법

- 개념

• 최대 공약수

  • 유클리드 호제법: 최대 공약수를 구하는 알고리즘

    "2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다."

    간단히 설명하면 어떤 수에 대해 위의 과정을 계속 반복해 나머지가 0이 나올 때까지 나누면 그 수가 바로 최대공약수라는 소리다.

    1071과 1029의 최대공약수를 구하면,
    1071은 1029로 나누어 떨어지지 않음 -> 1071을 1029로 나눈 나머지를 구한다. ≫ 42
    1029는 42로 나누어 떨어지지 않음 -> 1029를 42로 나눈 나머지를 구한다. ≫ 21
    42는 21로 나누어 떨어진다.
    => 1071 & 1029 의 최대 공약수: 21

  • 파이썬 구현 코드

    def gcd(a, b): # gcd(Greatest Common Divisior)
      if a < b: b, a = a, b # a 가 더 큰 수로
      if b == 0: 
          return a
      else:
          return gcd(b, a % b) # r == a % b 
     

    
    

• 최대 공배수: 두 자연수의 곱 / 최대공약수

코드

def gcd(a, b): #a 가 더 큰 수로 가정
    if a < b: b, a = a, b
    if b == 0: 
        return a
    else:
        return gcd(b, a % b)
    
def lcm(m, g):
    return m // g
    
def solution(n, m):
    g = gcd(n, m)
    l = lcm(n*m, g)
    
    return [g, l]

최적 코드

• 풀고 보니 python 3.5 부턴 gcd 함수가 있다더라.
  from math import gcd...
  ** lcm 함수는 3.9 부터 들어왔서 대부분의 3.8 버전의 코테에서 에러남.

import math import gcd

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