[백준] 2609 최대공약수와 최소공배수
2021. 9. 26. 10:00ㆍ프로그래밍 공부/알고리즘
반응형
SMALL
문제출처] https://www.acmicpc.net/problem/2609
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
문제요약
최대공약수와 최소공배수를 구하는 문제
풀이
최대공약수와 최소공배수를 구하는 중학교 때 배운 방법은 소인수 분해를 통한 방법이다.
그러나 소인수 분해를 이용하여 알고리즘을 작성할 경우 성능이 떨어지므로 유클리드 호제법을 이용하였다. 유클리드 호제법은 유키피디어를 참고하였다.
https://ko.wikipedia.org/wiki/유클리드_호제법
유클리드 호제법 - 위키백과, 우리 모두의 백과사전
유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를
ko.wikipedia.org
유클리드 호제법은 간단하게 구현할 수 있다.
GCD를 계산할 때 a가 항상 b보다 크게 유지되기 위하여 조건문을 통하여 통제해주었다.
그 후 while문을 통하여 GCD에서 작은 수(b)가 0이 될 때까지 수행해준다.
소스코드는 Python 3으로 작성되었습니다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
def gcd(a, b):
# 무조건 a > b 유지
if a > b:
pass
else:
a, b = b, a
while b > 0:
r = a % b
a, b = b, r
return a
g = gcd(n, m)
l = n * m // g
print(g, l, sep='\n')
반응형
LIST
'프로그래밍 공부 > 알고리즘' 카테고리의 다른 글
[백준] 3036 링 (0) | 2021.09.27 |
---|---|
[백준] 1934 최소공배수 (0) | 2021.09.26 |
[백준] 1037 약수 (0) | 2021.09.25 |
[백준] 18870 좌표 압축 (0) | 2021.09.23 |
[백준] 15649 N과 M (1) (0) | 2021.09.21 |