목록2025/01/04 (1)

FE PARADISE

유클리드 호제법 - 최대공약수 구하기 (자바스크립트 코드)

유클리드 호제법 (유클리드 알고리즘)두 양의 정수 혹은 다항식의 최대공약수를 구하는 방법이다. 두 자연수 a,b에 대해 r = a % bgcd(a,b) = gcd(b,r)r을 a를 b로 나눈 나머지로 정의할 시 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 그럼 b와 r의 최대공약수를 구해야 하는데 이때 b를 r로 나눈 나머지를 r2라고 할 경우, b와 r의 최대공약수는 r과 r2의 최대공약수와 같다. 만약 r을 r2로 나눈 나머지값이 0일 경우 r2가 최대공약수이다. 만약 그렇지 않을 경우, 위와 같은 과정을 나머지 값이 0이 나올 때까지 반복하여 최대공약수를 구한다.예시를 보자.a = 56, b = 21 이 두 수에 대한 최대공약수 gcd(56, 21) 를 구하여 보자. 우선 a를 b로 나눈 ..
자료구조 & 알고리즘 2025. 1. 4. 16:14
이전 Prev 1 Next 다음