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

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

 

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

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

이 문제를 해결하기 위해선 유클리드 호제법을 알아야 합니다.

유클리드 호제법 : 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘이다.

 

• 호제란 ?
  • 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다.

예시

• 1071은 1029로 나누어떨어지지 않기에 1071을 1029로 나눈 나머지를 구한다. -> 42
• 1029는 42로 나누어떨어지지 않기에 1029를 42로 나눈 나머지를 구한다. -> 21
• 42는 21로 나누어떨어진다.
• 그래서 최대공약수는 21이다.

def solution(n, m):
    a,b = max(n,m),min(n,m)
    t = 0
    while b>0:
        t = a%b
        a,b = b,t
    return [a,n*m/a]

여기서 흥미로웠던 점은 a,b = b,t 코드와 같이 swap코드로 값을 대입변경한다는 점이다. 이렇게 간단하게 값을 대입시킬 수 있다는 점을 기억해야겠다. 그리고 최소공배수는 두 수의 곱에 최대공약수를 나눈 값으로 n*m/a로 표현된다.