최대공약수3 2609번: 최대공약수와 최소공배수 - 문제 사이트: https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 입력된 두 수의 최대공약수와 최소공배수를 구하는 문제이다. "1934번: 최소공배수" 문제의 풀이법으로 해결하였다. #include using namespace std; int getGCD(int A, int B) { return B ? getGCD(B, A % B) : A; } int main() { int A, B; cin >> A >> B; int gcd = getGCD(A, B); cout 2023. 6. 25. 기약분수 기약분수(Irreducible Fraction)는 분자와 분모의 공약수 (Greatest Common Factor, GCF)가 1뿐이어서 더이상 약분되지 않는 분수이다. 분자와 분모를 1 이외의 공통된 약수로 나누는 행위를 약분(Reduction of a fraction) 이라고 한다. 정수 a,b에 대해, 분수 a/b가 기약분수라는 것과, a,b가 서로소 즉, 최대공약수가 1이라는 것은 같은 의미이다. [출처] 위키백과 - 기약분수 기약분수는 분모와 분자의 최대공약수를 구한 뒤 분모와 분자에 각각 나눠주면 된다. (예) 분모: 120, 분자: 90 == 최대공약수: 30 → 분모: 4, 분자: 3 이 때, 최대 공약수를 구하는 방법에는 유클리드 호제법 등이 있다. * 연관 문제: - [백준] 1735번.. 2023. 6. 20. 13241번: 최소공배수 - 관련 사이트: https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 자연수 A와 B의 최소공배수를 구하는 문제이다. "1934번: 최소공배수" 문제와 동일하지만, 유클리드 호제법으로 최대공약수를 구해야 한다는 조건이 있다. "1934번: 최소공배수" 의 두번째 풀이를 적용해주면 된다. 1) 유클리드 호제법을 이용하여 A, B 두 수의 최대공약수 확인 3) (A * B) /.. 2023. 6. 19. 이전 1 다음