유클리드 호제법1

• 유클리드 호제법: 두 수의 최대공약수 구하기 유클리드 호제법이란? 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법 중 하나로, 고대 그리스 수학자인 유클리드가 제안한 알고리즘으로, 매우 간단하면서 효과적인 방법 원리? 자연수 a와 b가 있다고 하면, a를 b로 나눈 나머지를 구한다. 나머지를 r이라고 한다. 나머지 r이 0이라면, b는 a와 b의 최대공약수이다. 따라서 알고리즘을 종료하고 b를 결과로 출력한다. 만약 나머지 r이 0이 아니라면, b를 a로 대체하고, r을 b로 대체한다. 다시 말해서 GCD(a, b) = GCD(b, r) 인 것이다. 식으로 풀면, a = bq + r 일 때 GCD(a, b) = GCD(b, r)이다 예시? 48과 18의 최대공약수(GCD)를 구해보면, 1. 48 % .. 알고리즘/개념 2023. 6. 19.