일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- solutions of matrix equation
- homogeneous linear system
- Big Theta
- nontrivial solution
- python
- trivial solution
- recursive algorithms
- Big-Oh 예제
- 일차변환
- 알고리즘 분석의 실례
- 코틀린 시작하기
- 랜덤 순서 배열
- Big-Oh notation
- matrix fo a linear transformation
- 이진 탐색
- one-to-one
- 빅오메가
- matrix-vector product
- itertools
- 배열 섞기
- 빅오 표기법
- nonhomogeneous linear system
- 코틀린 Hello World!
- NumPy
- 재귀함수
- Big-O 예제
- 빅세타
- Big Omega
- matrix trnasformations
- linear dependence
- Today
- Total
코딩 연습
예제로 알아보는 확장 유클리드 알고리즘 본문
유클리드 알고리즘
이 글을 이해하기 위해서는 유클리드 알고리즘을 먼저 이해해야 합니다. 다음 동영상을 참고하시기 바랍니다.
확장 유클리드 알고리즘
x,y 에 대한 부정방정식 ax+by=c 는 c 의 값이 gcd(a,b) 의 배수일 때만 정수해를 갖는다고 알려져 있다. 즉, ax+by=c 가 정수해를 갖는 c의 최솟값이 gcd(a,b) 가 되는 것이다. 따라서 확장 유클리드 알고리즘은 말 그대로 유클리드 알고리즘을 확장하여 a,b 의 최대공약수 뿐만 아니라, ax+by=gcd(a,b)를 만족하는 정수해 x,y 도 구하는 알고리즘이라고 생각하면 된다.
240 과 46 의 최대공약수를 c=gcd(240,46) 라고 할 때 부정방정식 240x+46y=c 의 정수해 및 c 를 구해보자.
먼저 유클리드 알고리즘을 적용하도록 하자.
- 240=46×5+10 이므로 10=240×1+46×(−5)
- 46=10×4+6 이므로 6=46−10×4=46−(i)×4=46−240×4+46×20=240×(−4)+46×21
- 10=6×1+4 이므로 4=10−6×1=(i)−(ii)×1=240×1−46×5−240×(−4)−46×21=240×5+46×(−26)
- 6=4×1+2 이므로 2=6−4×1=(ii)−(iii)×1=240×(−4)+46×21−240×5+46×26=240×(−9)+46×47
- 4=2×2+0 이므로 끝낸다.
결국 240 과 46 의 최대공약수는 2 이고, 240x+46y=2 를 만족하는 정수해는 x=−9,y=47 이 된다.
위의 연산 과정을 이해했다면 알고리즘을 프로그래밍에 적용시키는 것은 어려운 일이 아니다.
r0=a,r1=b
s0=1,s1=0
t0=0,t1=1
을 초기값으로 시작한다. 즉, 위의 예제에서는 r0=240,r1=46 이 되어
240=s0×r0+t0×r1
46=s1×r0+t1×r1
이 되는 것이다.
이제 다음의 식들로 r,s,t 값들을 업데이트 한다.
ri+1=ri−1−qiri
si+1=si−1−qisi
ti+1=ti−1−qiti
이때, qi 와 ri+1 은 각각 ri−1 을 ri 로 나눈 몫과 나머지가 된다.
이 연산과정은 rk+1=0 이 되면 멈추게 되고, gcd(a,b)=rk, 부정방정식 ax+by=rk 의 정수해는 x=sk,y=tk 가 되는 것이다.
파이썬을 이용하여 rk,sk,tk 을 반환하는 함수를 만들어 보면 다음과 같을 것이다.
def exeu(a, b):
r = [a, b]
s = [1, 0]
t = [0, 1]
while r[-1] != 0:
q = int(r[-2] / r[-1])
r.append(r[-2] - q * r[-1])
s.append(s[-2] - q * s[-1])
t.append(t[-2] - q * t[-1])
return (r[-2], s[-2], t[-2])
'알고리즘' 카테고리의 다른 글
(재귀함수) n! (n 의 계승) 구하기 (0) | 2017.04.29 |
---|---|
(재귀함수) 자(ruler)의 눈금 그리기 (1) | 2017.04.29 |
N-queens 문제 (0) | 2016.03.31 |
달팽이 배열 (5) | 2016.03.29 |
하노이의 탑 (0) | 2016.03.19 |