5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net 문제 두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. 출력 각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다. 코드 def gcd(a, b): if b > a: a, b = b, a if a % b == 0: return b return gcd(b, a..
최대공약수
2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 코드 # 최대공약수 def gcd(a, b): if b > a: a, b = b, a if a % b == 0: return b return gcd(b, a % b) # 최소공배수 def lcm(a,b)..
유클리드 호제법은 두 양의 정수, 또는 두 다항식의 최대공약수를 구하는 알고리즘이다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 말로 설명하자면 다음과 같다. 두 양의 정수 $a,b (a>b)$에 대하여 $a = bq + r (0 ≤ r a: a, b = b, a if a % b == 0: return b return gcd(b, a % b)$O((log N)^2)$의 시간복잡도로 최대공약수를..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 def gcd(a,b): if a % b == 0: return b else: return gcd(b, a%b) def solution(arr): lcm = arr[0] for i in range(1, len(arr)): lcm = lcm * arr[i] // gcd(lcm, arr[i]) return lcm 최소공배수, 최대공약수 구할 때는 유클리드 호제법을 사용한다. 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean al..
