알고리즘 문제해결기법
-
알고리즘 - 최대공약수 : 유클리드 호제법(Euclidean algorithm) GCDDev/알고리즘 2021. 5. 3. 19:24
유클리드 호제법 (BPEuclidean algorithm) GCD - 최대 공약수 구하기 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. - 위키백과 예시 2958, 1088 의 최대공약수를 구해보자 2958을 1088로 나눈다. 정확히 나누어지지 않기때문에 나머지를 구한다. 나머지 -> 782 1088을 782로 나눈다. 정확히 나누어지지 않기때문에 나머지를 구한다. 나머지 -> 306 782을 306로 나눈다. 정확히 나누어지지 않기때문에 나머지를 구한다. 나머지 -> 170 30..