http://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
학교 졸업후 이걸 쓰는 분이 많지 않은 지라 대부분의 직딩들은 기억이 나지 않을 것이다.
간단히 이야기 하자면, 두 자연수의 최대공약수(gcd) 를 구하는 알고리즘이다.
최대공약수까지 모르신다면...흠...고통스럽다...
어쨌거나...
알고리즘의 핵심은 두 자연수중 큰 수에서 작은 수를 나누어 "나머지"를 구하는 데 있다. 몫은 중요하지 않다.
mod 또는 % 연산 등이라고 할까나...'
그리고 이전 연산의 값중 작은 값을 얻어진 나머지로 다시 나누어 나머지를 구한다.
그리고... 이런 연산의 무한 반복이다...
단, 무한 반복은 항상 조건식이 있다!!
조건은 나머지가 0 (=zero) 이면 종료된다는 것....
def gcd(m,n):
while n != 0:
t = m%n
m = n
n = t
return abs(m)
예를 들어 두 자연수 1071 과 1029 의 gcd 를 구해보자.
1단계) 1071 % 1029 = 42 (% 는 나머지 구하는 연산)
2단계) 1029 % 42 = 21
3단계) 42 % 21 = 0 (드디어 나머지가 0이다!!)
그러면, 이때 gcd 는 21 이다.
학교 졸업후 이걸 쓰는 분이 많지 않은 지라 대부분의 직딩들은 기억이 나지 않을 것이다.
간단히 이야기 하자면, 두 자연수의 최대공약수(gcd) 를 구하는 알고리즘이다.
최대공약수까지 모르신다면...흠...고통스럽다...
어쨌거나...
알고리즘의 핵심은 두 자연수중 큰 수에서 작은 수를 나누어 "나머지"를 구하는 데 있다. 몫은 중요하지 않다.
mod 또는 % 연산 등이라고 할까나...'
그리고 이전 연산의 값중 작은 값을 얻어진 나머지로 다시 나누어 나머지를 구한다.
그리고... 이런 연산의 무한 반복이다...
단, 무한 반복은 항상 조건식이 있다!!
조건은 나머지가 0 (=zero) 이면 종료된다는 것....
def gcd(m,n):
while n != 0:
t = m%n
m = n
n = t
return abs(m)
예를 들어 두 자연수 1071 과 1029 의 gcd 를 구해보자.
1단계) 1071 % 1029 = 42 (% 는 나머지 구하는 연산)
2단계) 1029 % 42 = 21
3단계) 42 % 21 = 0 (드디어 나머지가 0이다!!)
그러면, 이때 gcd 는 21 이다.
반응형
'Algorithm' 카테고리의 다른 글
| 문자열(string) 필수 기능 (0) | 2007.09.14 |
|---|---|
| 디피 헬만(Diffe-Hellman) 알고리즘 이해하기 (0) | 2007.09.14 |
| 과연 정렬 알고리즘을 몇 가지 이상 알아야 훌륭한 개발자인가? (2) | 2007.09.04 |
| 정팔각형과 계산... (2) | 2007.08.31 |
| 정팔각형 (0) | 2007.07.06 |
