최대공약수와 최소공배수/ 개발/ProblemSolving / 2019.12.22
최대공약수 최대공약수를 구하는 알고리즘으로 유명한 유클리드 호제법이 있습니다. "두 개의 자연수 a, b에서 a를 b로 나눈 나머지 r이 있을 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다." 이 원리를 이용하여 a, b가 있을 때 b MOD r를 구하고 이를 r'라고 하면, r MOD r'를 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다. (gcd) 그대로 코드로 표현해보면 int gcd(int a, int b) { int r; while(b) { r = a % b; a = b; b = r; } return a; } 단, a > b는 이어야하기 때문에 b > a라면 두 숫자를 바꿔주는 과정이 필요합니다. int gcd(int a, int b) { if(b > a) ..