GCD

최소공배수란? 두 수 이상이 공통으로 가지는 배수 중 가장 작은 값을 의미합니다. 예시숫자배수1212, 24, 36, 48, 60, 72, ...1818, 36, 54, 72, ... 두 수 12와 18의 공통 배수는36, 72, ... 입니다. 👉 이 중 가장 작은 수는 36입니다.즉, 최소공배수 LCM(12, 18) = 36 입니다. 특징두 수가 공통으로 나눌 수 있는 가장 작은 배수반복되는 주기를 찾을 때 유용최대공약수와 곱셈 관계로 연결됨실무에선 최대공약수(GCD)를 이용해 빠르게 계산 최대공약수와 최소공배수의 차이구분의미예시 (12, 18 기준)최대공약수 (GCD)두 수를 나눌 수 있는 가장 큰 수6최소공배수 (LCM)두 수로 나눌 수 있는 가장 작은 수36 📌 공식 관계GCD(a,b..

최대공약수란(GCD)?두 수 이상에서 모두 나누어 떨어지는 가장 큰 수를 의미합니다. 예시숫자약수121, 2, 3, 4, 6, 12181, 2, 3, 6, 9, 18 두 수 12와 18의 공통 약수는1, 2, 3, 6 입니다. 👉 이 중 가장 큰 수는 6입니다.즉, 최대공약수 GCD(12, 18) = 6 입니다. 특징두 수의 공통된 약수 중 가장 큰 수나눗셈 연산을 활용하여 빠르게 계산 가능최소공배수와는 공식적으로 연관됨수학뿐 아니라 코딩 테스트, 암호학 등에도 활용 실습 예제1) 기본 방식 (모든 약수 검사)// 기본 약수 검사 방식public static int basicGCD(int a, int b) { int gcd = 1; for (int i = 1; i ❌ 단점: 반복이 많아..