728x90 kotlin 26091 [알고리즘] 유클리드 호제법 + [백준 2609번] (Kotlin) 유클리드 호제법이란? 2개의 자연수쌍의 최대공약수를 구하는 알고리즘입니다. 또한, 최대공약수를 이용하여 최소공배수를 구할 수 있습니다. 최대공약수 (GCD, Greatest Common Divisor) 2개의 자연수 a, b에 대해 a를 b로 나눈 나머지를 r이라 할 때, a와 b의 최대공약수는 a와 r의 최대공약수와 같습니다. 이 과정을 반복하여 나머지가 0이 되었을 때 나누었던 수가 a와 b의 최대공약수입니다. ☞ 예를 들어 (a= 24, b= 18)에 대해 최대공약수를 구해보겠습니다. 이때, r= a%b = 6이고 다시 b를 r(a%b)로 나누면 나머지가 0이 되어 최대공약수는 6이 됩니다. 최소공배수 (LCM, Least Common Multiple) 최소공배수는 위에서 구한 최대공약수를 활용해 .. 2023. 1. 25. 이전 1 다음 728x90 반응형