최근에 모르는 알고리즘이 너무 많아서.. 한계를 많이 느낀다..
그래서 Introduction to Algorithms (일명 CLR) 책에있는 알고리즘들 하나씩 볼 참이다..

그 첫번째로.. 찾아본 부분이 오래전부터 궁금했던 Modular Arithmetic..
오호.. 생각보다 재밌는 내용이 많다..~

GCD (Greatest Common Divisor) 를 구하는 방법중에 가장 빠른 방법이..
바로 Euclidean Algorithm (유클리드 호제법) 이다..
(내가 아는거중에 가장 빠른 방법이다..;; 더 빠른게 있는지도 모름.. ㅋ)

식도 매우 간단해서.. C언어로 구현한다면 10초만에 구현 완료할 수 있다..~

gcd(a, b) = gcd(b, a mod b)


그런데 위에 알고리즘을 이용해서 뭔가 유용한걸 하나 만들어냈는데..
다음과같은 식을 생각해 보자..

d = gcd(a, b) = a*x + b*y

a와 b가 input으로 주어질 때, x, y, d를 찾아주는 알고리즘이 바로 Extended Euclid 이다..

예)

 a   b   a/b   d    x     y
------------------------------
99  78    1    3  -11    14
78  21    3    3    3   -11
21  15    1    3   -2     3
15   6    2    3    1    -2
 6   3    2    3    0     1
 3   0    -    3    1     0


CLRS 책에있는 pseudo code..

EXTENDED-EUCLID(a, b)
1   if b = 0
2       then return (a, 1, 0)
3   (d', x', y') <- EXTENDED-EUCLID(b, a mod b)
4   (d, x, y) <- (d', y', x' - (a/b) * y')
5   return (d, x, y)

(참고: line 4에서 a/b는 quotient 이다)


자.. 이제 UVa 10104 - Euclid Problem 을 풀 수 있다.. ㅋㅋ


'Problem Solving > Algorithm notes' 카테고리의 다른 글

Sorting Algorithm O(n^2)  (0) 2009.08.31
Bell Number  (0) 2009.07.12
Finding Minimum Path Cover in DAG  (0) 2009.06.15
Plane Equation (평면의 방정식)  (0) 2009.04.16
Ellipse (타원)  (0) 2009.04.15
Modular Arithmetic 1탄 - Extended Euclid  (2) 2009.02.22
Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07
Josephus Problem  (2) 2009.01.01
Number of Swap Operations  (0) 2008.07.24
소수 구하는 방법 (Sieve of Eratosthenes)  (2) 2008.07.15
Horner's Rule  (0) 2008.05.04

Comments

  1. mynotepad 2009.02.25 21:57 신고 Permalink Modify/Delete Reply

    ㅋㅋ 덕분에 나도 10104 풀었넹... 땡큐...
    앞으로도 algorithm 관련 article 자주 좀 올려봐...

    • helloneo 2009.02.25 23:46 신고 Permalink Modify/Delete

      음.. 유클리드알고리즘이 뒤에 디오판토스방정식이랑 chinese remainder theorem이랑 이어지는데.. 이해를 못하고있어요.. ㅠㅠ

Leave a Comment


to Top