최대공약수와 최소공배수
[BOJ] 2609 최대공약수와 최소공배수 (Python / 파이썬)
[BOJ] 2609 최대공약수와 최소공배수 (Python / 파이썬)
2021.07.30🧷 문제 https://www.acmicpc.net/problem/2609 두 개의 자연수를 입력받아 최대공약수와 최소공배수를 출력하는 문제이다. 🛠 풀이 이 문제는 유클리드 호제법을 이용해 최대 공약수와 최소 공배수를 구하면 된다. Step 1. 유클리드 호제법을 이용해 최대공약수를 구한다. 유클리드 호제법 : 2개의 자연수의 최대공약수를 구하는 알고리즘이다. "a와 b의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다."두 수 x와 y가 있을 때, (단, x >= y) def gcd(x, y): while b > 0: a, b = b, a % b return a 🖊 나의 코드 import sys input = sys.stdin.readline def GCD(a, b): while b > ..