※ 본 사진과 해당 게시글 내용의 문제 모두 프로그래머스[Programmers]사이트에 발췌해왔습니다.

💬 들어가기 앞서..

💢 LCM과 GCD 란?

• LCM (Least Common Multiple) : 최소 공배수

• GCD (Greatest Common Divisor) : 최대 공배수

💢 유클리드 호제법 (Euclidean algorithm) 이란?

직설적으로 유클리드 알고리즘이라고도 불린다.
유클리드 호제법은 최대공약수를 구하는 알고리즘 중 하나인데
"호제법 "이란 말은 "두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘"을 나타낸다.

[자연수 a, b]에 대해서 a를 b로 [나눈 나머지를 r]이라 하면(단, a>b) ,
"a와 b 최대공약수" 는 "b와 r 최대공약수"와 같다.

이 성질을 이용하여
처음 구했던 나머지(r)을 다시 나눠 나머지를 구하고 다시 위 과정을 반복하여
"나머지가 0이 되었을 때" 나누는 수가
a와 b의 최대 공약수가 된다.

a % b = r 
b % r = (b%r)

#반복과정
r % (b%r) = (r%(b%r))
(b%r) % (r%(b%r)) = ((b%r)%(r%(b%r)))
...
..

위 과정을 반복하다가 어느 순간, 나머지가 0이 되는 순간,
(이전 과정에서의) 나머지 값이였던 값 → 처음 두 수의 최대공약수가 되는 원리이다.

※ 출처 ㅣ 위키백과_유클리드 호제법

❓ 문제

문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 
배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 

예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 
solution(3, 12)는 [3, 12]를 반환해야 합니다.


제한 조건 : 두 수는 1이상 1000000이하의 자연수입니다.

❗ 풀이

My Code

def solution(n, m):
    x, y = n, m
    while y:
        x, y = y, x % y
        #y가 0이 될때까지 y를 x%y(두수의 나머지 값)로 돌리면서 나눠감
    return [x, (n * m) // x]

위 유클리드 알고리즘에서 가장 중요한 순간인 "나머지 r이 0이 되는 순간"을
while문을 통해 y 위치의 수가 0 (False)가 되는 순간 반복문이 종료되는 기능을 활용해 설정했다.

x, y = n, m 로 임의의 변수에 입력값 n과 m을 대입한 이유는
마지막 return할 때, "while문을 통해 얻은 최대공약수 ( while문에서의 마지막 x)" 를 이용해 최소공배수를 구하기 위함이다.
(위 유클리드 알고리즘 설명에서는 n이 m보다 커야한다고 했지만 "m이 더 크더라도" 나머지 연산 %를 하게 되면 m 자체가 나머지 r 값으로처리가 되기때문에 x, y 자리에 대입되고 다시 정상적인 계산이 처리되기 때문에 별도의 조건을 설정치 않아도 된다. )

루프(Loop)문 While을 통해 얻은 최대공약수 x를
처음 입력값 a,b의 곱에 나눠준 값 최소공배수로 x와 함께 Return하면 된다.

이는
두 수의 곱에 최대공약수를 나누면 최소공배수가 되는 성질을 이용한 것이다.
(x는 최대공약수이기 때문에 두 수의 곱에 나누더라도 나머지는 0이기 때문에 //연산자가 아닌 /연산자를 사용해도 된다.)

❣ 다른 풀이

(1)

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

이 해결방법에서는
처음부터 max()와 min()을 통해 큰값을 앞으로 배치하여 계산을 시작했고
임의의 변수 t에 1을 대입하여 while문 종료 조건을 t >0으로 설정하여 투입되어
다시 나머지 값으로서의 역할의 변수로 재선언하고
나머지 t가 0이 되는 순간 (while문 종료) 이전에 구했던 직전 나머지 값 c를 최대공약수로 가져왔다.

최대공배수를 구하는 방식은 필자의 방식과 같이 투입값 a, b를 이용하여 (a*b)/c 식을 사용했다

(2)

import math

def gcdlcm(a, b):
    return [math.gcd(a,b) , math.lcm(a,b)]

두 함수는 math 라이브러리에 속해있는 "최대 공약수 & 최소 공배수"함수이다.
단, 두 함수 모두 비교적 최근에 추가된 함수이기 때문에 gcd()함수는 Python 3.5 이상, lcm()함수는 Python 3.9 이상이여야 한다.