Modular Arithmetic 1탄 - Extended Euclid
Problem Solving/Algorithm notes 2009.02.22 01:08
최근에 모르는 알고리즘이 너무 많아서.. 한계를 많이 느낀다..
그래서 Introduction to Algorithms (일명 CLR) 책에있는 알고리즘들 하나씩 볼 참이다..
그 첫번째로.. 찾아본 부분이 오래전부터 궁금했던 Modular Arithmetic..
오호.. 생각보다 재밌는 내용이 많다..~
GCD (Greatest Common Divisor) 를 구하는 방법중에 가장 빠른 방법이..
바로 Euclidean Algorithm (유클리드 호제법) 이다..
그래서 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 이다..
CLRS 책에있는 pseudo code..
(참고: line 4에서 a/b는 quotient 이다)
자.. 이제 UVa 10104 - Euclid Problem 을 풀 수 있다.. ㅋㅋ
식도 매우 간단해서.. 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
------------------------------
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)
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
ㅋㅋ 덕분에 나도 10104 풀었넹... 땡큐...
앞으로도 algorithm 관련 article 자주 좀 올려봐...
음.. 유클리드알고리즘이 뒤에 디오판토스방정식이랑 chinese remainder theorem이랑 이어지는데.. 이해를 못하고있어요.. ㅠㅠ