0과 1의 쉼터

목차유클리드 호제법 (Euclidean Algorithm)확장 : GCD와 LCM의 관계math.gcd / math.lcm✏️ 연습 문제유클리드 호제법 (Euclidean Algorithm)두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘원리두 수 a와 b 의 최대공약수는 a를 b로 나눈 나머지 r과 b의 최대공약수와 같습니다.즉, GCD(a, b) = GCD(b, a % b)가 성립합니다. 💡나머지가 0이 될 때 탐색을 종료합니다def gcd(a, b): return a if b == 0 else gcd(b, a % b)# 예제print(gcd(48, 18)) # 출력: 6⌛ 시간 복잡도유클리드 호제법의 시간 복잡도는 a > b에 대해 최대 b의 자릿수..

문제https://www.acmicpc.net/problem/2436 풀이두 수 A, B의 GCD, LCM이 주어질 때, 두 수의 합이 최소가 되는 수를 구하는 문제다.이때 두 수의 범위 2 ~ 1억에 대해 GCD, LCM을 전부 구해 비교하는 방법은 시간 초과가 발생한다.탐색 범위를 좁혀보자.$G = GCD(A, B), L = LCM(A, B)$일 때, $AB = GL$, $A = Gx$, $B = Gy$이므로 $AB = G^2xy = GL, xy = \frac{L}{G} = K$가 성립한다.K의 모든 약수 쌍 중 $GCD(A, B) = G*GCD(x, y)$를 만족해야 하므로, $GCD(x, y) = 1$인 약수만 해당된다. K = LCM // GCD x, y = 0, 0 for d ..

문제https://www.acmicpc.net/problem/1934 풀이주어진 두 자연수 A, B에 대해 LCM을 구하는 기초 문제다.두 수의 곱을 GCD로 나누면 구할 수 있다.def lcm(a, b): return int(a * b / gcd(a, b))소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/01934.py