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. 유클리드 알고리즘
  1.   기술공통
  2.   기초과학
        1. 과학
    1.   수학
          1. 수학
      1.   기초수학
      2.   집합,논리
      3.   해석학(미적분 등)
      4.   대수학
            1. 대수학
        1.   기초대수학
        2.   정수론(수론)
              1. 정수론
              2. 절대값
              3. 짝수,홀수,패리티
          1.   수의 구분
          2.   셈법(Counting)
          3.   나눗셈(가분성)
            1.   1. 약수,배수
                2. 나눗셈 관계식
                3. 잉여류,잉여계
          4.   소수,최대공약수
          5.   디오판투스 방정식
          6.   합동
        3.   선형 대수학
        4.   추상대수학
      5.   확률/통계
      6.   수치해법
    2.   물리
    3.   화학
    4.   지구,천체 과학
    5.   생명과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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