[Algorithm] 최대공약수 GCD (유클리드 호제법)

호제법 두 수가 서로 상대방 수를 나눠서 결국 원하는 수를 얻는 알고리즘 두 수 A, B의 최대공약수를 G라고 하면 A = Ga / B = Gb → A를 B로 나누면 (A≥B라고 가정) A = BQ + R → Q : 몫, R : 나머지 Ga = GbQ + R R = G(a-bQ) ≫ G는 A를 B로 나눈 나머지의 약수 Example A : 20 / B : 55 → GCD(A, B) 20%55 = 20 → GCD(55, 20) 55%20 = 15 → GCD(20, 15) 20%15 = 5 → GCD(15, 5) 15%5 = 0 → GCD(5, 0) → B가 0이 되는 순간 알고리즘 종료 → 최종 최대공약수 = A Java Code static int GCD(int A, int B){ if(B==0) ret..

2022.01.24