[ Algorithm/알고리즘 ]
유클리드 호제법(Euclidean Algorithm)
2024-05-16 13:51:06
유클리드 알고리즘과 호제법 ☞ 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. ☞ 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.최대공약수(GCD: Greatest Common Divisor) & 최소공배수(LCM: Least Common Multiple)란?☞ 최대공약수(GCD: Greatest Common Divisor): 두 수의 공통된 '약수 중에서 가장 큰 수'를 의미한다.☞ 최소공배수(LCM: Least Common Multiple): 두 수의 공통된 '배수 중에서 가장 작은 수'를 의미한다.두 수의 최대공약수, 최소공배수 구하기최대공약수(GCD) 구현 방법1. 반복문으로 구현b가 0..