Alex Han: Coding Explorer

https://www.acmicpc.net/problem/5347 1. 문제두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. 출력각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다. 예제 입력315 2133 229 10 예제 출력1056690 해결 코드GCD를 효율적으로 구할 수 있다면 LCM은 손쉽게 구할 수 있다.import java.util.Scanner;public class Main { public static long GCD(long m, long n) { ..

0. 먼저 읽어보기 GCD 알고리즘 GCD(최대공약수, Greatest Common Divisor) 알고리즘1. GCD(최대공약수)란?두 숫자를 나눌 수 있는 가장 큰 숫자를 찾는 것이라고 보면 된다. 예를 들어, 48과 18의 최대공약수(GCD)는 6이다.왜냐하면 6은 48도 나누고, 18도 나누는 가장 큰 수이기 때문이jyhan0625.tistory.com   https://www.acmicpc.net/problem/5344 1. 문제The greatest common divisor (GCD) of two integers is the largest positive integer that divides the numbers without a remainder. For example, GCD of 8 a..

1. GCD(최대공약수)란?두 숫자를 나눌 수 있는 가장 큰 숫자를 찾는 것이라고 보면 된다. 예를 들어, 48과 18의 최대공약수(GCD)는 6이다.왜냐하면 6은 48도 나누고, 18도 나누는 가장 큰 수이기 때문이다.   2. 가장 쉬운 방법 (완전탐색)모든 숫자를 하나씩 확인하면서 공약수를 찾고, 가장 큰 걸 선택하는 방법이다. ✅ 방법1부터 두 수 중 작은 숫자까지 하나씩 나누어보고, 둘 다 나눠지는 가장 큰 수를 선택한다. ❌ 단점숫자가 커지면 너무 오래 걸린다. 예를 들어, 1,000,000,000 같은 큰 숫자를 다 확인하려면 시간이 너무 많이 든다. 📌 코드 예제def gcd_brute_force(a, b): for i in range(min(a, b), 0, -1): ..