[알고리즘] 유클리드 호제법 - 최대공약수 / 최소공배수 구하기
▶️ 유클리드 호제법 : 유클리드 알고리즘, 최대 공약수 구하는 알고리즘 소인수분해 후 공통된 소수를 찾으면 된다. a, b를 나누어 떨어지게 하는 수 중 가장 큰 수 찾기 > 유클리드 알고리즘은 쉽게 말하면 MOD(나머지 구하기)라고 할 수 있다. ▶️예시 24와 18의 최대공약수(GCD) i) A = 24 / B = 18 인 경우 GCD(24, 18) -> GCD(18, 6) -> GCD(6, 0) = 6 a) 24 % 18 = 6 b) 18 % 6 = 6 (최대공약수) c) 6 % 6 = 0 278과 192의 최대공약수(GCD) ii) A = 278 / B = 192 인 경우 GCD(278, 192) -> GCD(192, 78) -> GCD(78, 36) -> GCD(36, 6) -> GCD(6, ..
2024. 3. 12.
