최대공약수(GCD) 와 최소공배수 (LCM)
최대공약수(GCD : Greatest Common Divisor) 최대공약수는 줄여서 GCD라 불림. 두 수 A,B의 최대공약수 G는 A,B의 공통된 약수 중에서 가장 큰 정수. (약수: N을 나눌수 있는 수) 최대공약수를 빠르게 구하는 방법 - 유클리드 호제법을 사용 GCD(a,b) = GCD(b,r) r이 0이면 그 때 b가 최대 공약수가 된다. ex) GCD(24,8) = GCD(16,8) = GCD(8,0) = 8 최대공약수 구현 재귀함수를 사용한 유클리드 호제법 int gcd(int a, int b){ if(b==0){ return a; } else{ reutnr gcd(b,a%b); } } 세 수의 최대공약수 GCD(a,b,c) = GCD(GCD(a,b),c) N개의 수 도 같은 방식으로 구할..
2023. 1. 2.
