Euclidean Algorithm   유클리드 알고리즘

(2018-01-09)

유클리드 호제법

1. 유클리드 호제법/알고리즘 (Euclidean Algorithm)최대공약수를 구하는 통상적인 방법으로는,
     - 두 수를 소인수분해한 후, 그 중 공통되는 소수 중 제일 큰 것을 찾아가는 복잡한 방법을 씀
        . 소인수분해(어떤 수를 소수의 곱셈 형태로 인수분해하는 것) 자체도 쉽지 않음

  ㅇ 유클리드 호제법/알고리즘
     - 두 정수의 최대공약수를 빠르게 계산해내는 알고리즘
        . 두 수의 나눗셈을 반복하여 나머지가 0이 될 때 최대공약수가 구해지는 방법
       
ㅇ 입력 : r[0], r[1]
ㅇ 출력 : gcd ( r[0], r[1] )

Euclidean ( r[0], r[1] ) {
    초기화 : i = 1 ;
    while ( r[i] ≠ 0 ) {
       r[i] = r[i-2] mod r[i-1] ; 
    }
    return gcd ( r[0], r[1] ) = r[i-1]
}
ㅇ 例) gcd(21,9) → a = 21, b = 9 - a = b x q + r - 21 = 9 x 2 + 3 → b = 9, r = 3 . 여기서, 나온 나머지로 방금 나누는데 사용한 수를 나눔 - 9 = 3 x 3 + 0 → b = 3, r = 0 . 여기서, 나머지가 0이 되므로, 이때 나눈 수가 최대공약수가 됨 - 따라서, gcd(21,9) = 3 ※ 결국, 유클리드 알고리즘은, - 단순히 나눗셈 만 되풀이하는 것 만으로도 최대공약수가 구해지게 됨 . 즉, 나눗셈을 되풀이하다가 마지막에 나누어떨어질 때의 나눈 수가 최대공약수가 됨 ※ 한편, 마지막이 1이 되는 경우(두 수의 최대공약수가 1 인 경우)에, - 이 때의 두 수는 서로소(Relatively Prime) 라고 함


[알고리즘 종류] 1. 알고리즘 분류 2. 탐색 알고리즘 3. 정렬 알고리즘 4. 그래프 알고리즘 5. 해쉬 알고리즘 6. 해싱 탐색 7. 최대 최소 구하기 8. 유클리드 알고리즘

 
        최근수정     요약목록(시험중)     참고문헌