프로그래머스 lv1 최대공약수와 최소공배수(연습문제)

문제 설명

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

제한 사항

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

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1

위의 설명과 같습니다.

입출력 예 #2

자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

출처: 프로그래머스 코딩 테스트 연습 (https://programmers.co.kr/learn/challenges)

풀이

answer = []
def compute_gcd(n, m):
    while m != 0:
        t = n%m
        (n,m) = (m,t)
    answer.append(abs(n))
    return abs(n)

def solution(n, m):
    lcm = (n*m)//compute_gcd(n, m)
    answer.append(lcm)
    return answer

solution(2,5)

0은 거짓이고 1은 참. while(y): 이뜻은? y가 0이 되면 1이면 계속.
while m !=0은? m이 0이 아니면 계속. 0이 되면 종료.
LCM = x,y를 곱한 후 최대공약수(GCD)로 나누면 됨

# 다른 사람 풀이2

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

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(gcdlcm(3,12))

최대 공약수, 최소 공배수 알고리즘

위키 유클리드 호제법

hackerrank 링크

programiz 링크

유클리드 호제법 정리

출처: 위키 유클리드 호제법 유클리드 호제법은 두 수를 서로(互) 나누어서(除:덜 제) 원하는 수를 얻는 알고리즘을 말한다.
a % b = r (단, a>b) 일때 a와 b의 GCD(Great Common Divisor)는 b와 r의 GCD와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여
나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 《원론》 제7권, 명제 1부터 3까지에 해당한다.

알고리즘

입력으로 두 수 m,n(m>n)이 들어온다.

n이 0이라면, m을 출력하고 알고리즘을 종료한다.

m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.

그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.
위 과정은 “n, m에 대해서 나머지 연산을 실시할 수 있다”라는 조건에만 의존하므로, 정수환뿐 아니라, 임의의 유클리드 정역에 대해도 똑같은 과정을 거치면 공>약인자가 구해진다.

소스코드1

def gcd(m,n):
	if m < n:
		m, n = n, m
	if n == 0:
		return m
    if m % n == 0:
		return n
	else:
		return gcd(n, m%n)

소스코드2

def gcd(m,n):
    while n!= 0:
       t = m%n
      (m,n) = (n,t)
    return abs(m)

소스코드3

def gcd(m,n):
    while n!= 0:
	    if m < n:
		    m, n = n, m
	    if n == 0:
		    return m
	    if m % n == 0:
		    return n

소스코드4

def gcd(m,n):
    if n == 0:
        return m
    mod = m % n
    if mod != 0:
        m, n = n, mod
        return gcd(m, n)
    else:
        return n

GCD를 이용해서 LCM(least common multiple) 구하기

# Python program to find the L.C.M. of two input number

# This function computes GCD 
def compute_gcd(x, y):

  while(y):
      x, y = y, x % y
  return x

# This function computes LCM
def compute_lcm(x, y):
  lcm = (x*y)//compute_gcd(x,y)
  return lcm

num1 = 54
num2 = 24 

print("The L.C.M. is", compute_lcm(num1, num2))