본문 바로가기

Algorithm/Algorithm 공부

(1)

최초의 알고리즘 중 하나! 유클리드 호제법으로 최대공약수 구하기 유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법 중 하나로, 인류 최초의 알고리즘 중 하나로서도 알려져 있습니다. 두 수 a와 b의 최대공약수를 구하기 위해서는, 다음과 같은 과정을 반복합니다. a를 b로 나눈 나머지 r을 구합니다. 만약 r이 0이면, b가 a와 b의 최대공약수가 됩니다. 즉, GCD(a, b) = b입니다. 만약 r이 0이 아니라면, b와 r의 최대공약수를 구하기 위해, 다시 b를 r로 나눕니다. 이때, r이 0이 될 때까지 반복합니다. fun gcd(a: Int, b: Int): Int { if (b == 0) return a return gcd(b, a % b) } 예를 들어, 54와 2..

티스토리툴바