CS/Algorithm
[Algorithm] 유클리드 호제법: 최대공약수/최소공배수 계산하기
유클리드 호제법(Euclidean algorithm)은 두 정수의 최대 공약수를 구하기 위한 알고리즘이다. 왜 공식이 아니라 알고리즘인가 했는데, 값을 구하기 위해 정해진 규칙에 따라 단계의 절차를 밟아 계산을 진행하기 때문에 그렇다고 한다. 기원전 300 원경에 나와서 지금까지 쓰이는 중이다. 이후 나올 약어들만 정리하고 가자면: \(GCD\): Greatest Common Divisor. 최대공약수 \(LCM\): Least Common Multiple. 최소공배수 유클리드 호제법: 최대공약수 계산 유클리드 호제법이 성립하기 위한 정리는 다음과 같다. 2개의 자연수 \(A, B\) 에 대해 \(A\)를 \(B\)로 나눈 나머지를 \(R\)이라 하자. \((A \geq B, 0 \leq R < B)\)..
