목록최대공약수 (1)

마이 플밍 블로그

[알고리즘] GCD 최대공약수 구하기 알고리즘

1. 유클리드 알고리즘(Euclidean algorithm) 두 자연수의 최대 공약수(greatest common divisor)를 찾는 알고리즘을 뜻한다. 2. 유클리드 알고리즘 원리 두수 A와 B(A>B)가 있고 A를 B로 나누었을때 나머지가 C일 때 C가 0일경우 B가 최대 공약수이고 아닐경우 A = B 로 B = A % B로 하고 반복해서 C가 0일 될때까지 하면 된다. ex) GCD(12, 8) -> GCD(8, 4) -> GCD(4, 0) 최소공배수 = 4 장점 최대공약수를 구하는 방법중 가장 간단한 방법인 1부터 min(A,B)까지 순서대로 찾는 방법의 시간 복잡도는 O(N)이지만 유클리드 호제법을 이용할 경우 O(Log N)으로 줄일 수 있다. 3. 구현(C/C++) 반복문을 통한 GCD ..
알고리즘 2022. 4. 29. 06:00
이전 Prev 1 Next 다음