문제:
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3,12의 최대공약수는 3, 최소공배수는 12이므로 solution(3,12)는 [3,12]를 반환해야 합니다.
풀이 방법:
최대공약수를 구하는 방법중 가장 좋은 방법은 유클리드 호제법을 사용하는 것이다. 작은 수의 경우에는 상관 없으나 문제와 같이 수가 커질 경우에는 유클리드 호제법이 효율적이기 때문이다.
유클리드 호제법이란 '정수 a,b,q,r(b!=0)에 대하여 a=bq+r이면 G(a,b)=G(b,r)가 성립한다.'라는 것이다. 따라서 이를 이용해 b가 0이 될 때가 while문을 반복하도록 해서 최대공약수를 구하도록 하였다.
최소공배수는 두 수의 곱에다가 최대공약수를 나누면 쉽게 구할 수 있다.
1 2 3 4 5 6 7 8 | def solution(n, m): gcd=n multi=n*m while m !=0: gcd,m=m,gcd%m lcm=multi/gcd answer = [gcd,int(lcm)] return answer | cs |
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 1. 정수 제곱근 판별 (0) | 2019.01.26 |
|---|---|
| [Programmers]Lv 2. 스킬트리 (0) | 2019.01.25 |
| [Programmers]Lv2. 탑 (0) | 2019.01.23 |
| [Programmers]Lv 1. 콜라츠 추측 (0) | 2019.01.21 |
| [Programmers]Lv 1. 하샤드 수 (0) | 2019.01.20 |