목록유클리드호제법 (1)

개발 블로그

유클리드 호제법

유클리드 호제법 유클리드 호제법(Euclidean algorithm)은 두 수의 최대공약수(GCD)를 효율적으로 구하는 고대의 알고리즘입니다. 이 방법은 두 수를 계속해서 나눗셈과 나머지 연산을 반복함으로써 최대공약수를 찾는 방식입니다.  *코딩테스트 준비용 알고리즘 학습을 위한 것이기 때문에 수학적 증명은 생략하겠씁니당   유클리드 호제법의 과정 다음과 같은 단계로 유클리드 호제법을 통해 최대 공약수를 구할 수 있습니다.1. 두 수 a, b를 MOD2. b와 나머지로 MOD3. 나머지가 0이 되는 순간의 b가 최대 공약수   최소공배수 lcm는 gcd를 이용하여 구하는 것이 일반적입니다. 아래에 반복문을 이용하여 최소공배수와 최대공약수를 구하는 함수를 작성하였습니다.import java.io.IOExc..
프로그래밍/알고리즘 2024. 10. 12. 00:47
이전 Prev 1 Next 다음