코딩 연습

예제로 알아보는 확장 유클리드 알고리즘 본문

알고리즘

예제로 알아보는 확장 유클리드 알고리즘

코딩아저씨 2016. 3. 17. 12:50
반응형

 

 

유클리드 알고리즘

이 글을 이해하기 위해서는 유클리드 알고리즘을 먼저 이해해야 합니다. 다음 동영상을 참고하시기 바랍니다.

 

 

 

 

확장 유클리드 알고리즘

x,y 에 대한 부정방정식 ax+by=cc 의 값이 gcd(a,b) 의 배수일 때만 정수해를 갖는다고 알려져 있다. 즉, ax+by=c 가 정수해를 갖는 c의 최솟값이 gcd(a,b) 가 되는 것이다. 따라서 확장 유클리드 알고리즘은 말 그대로 유클리드 알고리즘을 확장하여 a,b 의 최대공약수 뿐만 아니라, ax+by=gcd(a,b)를 만족하는 정수해 x,y 도 구하는 알고리즘이라고 생각하면 된다.

 

24046 의 최대공약수를 c=gcd(240,46) 라고 할 때 부정방정식 240x+46y=c 의 정수해 및 c 를 구해보자.

 

먼저 유클리드 알고리즘을 적용하도록 하자.

 

 

  1.  240=46×5+10 이므로 10=240×1+46×(5)
  2.  46=10×4+6 이므로 6=4610×4=46(i)×4=46240×4+46×20=240×(4)+46×21
  3. 10=6×1+4 이므로 4=106×1=(i)(ii)×1=240×146×5240×(4)46×21=240×5+46×(26)
  4. 6=4×1+2 이므로 2=64×1=(ii)(iii)×1=240×(4)+46×21240×5+46×26=240×(9)+46×47
  5. 4=2×2+0 이므로 끝낸다.

 

 

결국 24046 의 최대공약수는 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=ri1qiri

si+1=si1qisi

ti+1=ti1qiti

이때, qiri+1 은 각각 ri1ri 로 나눈 몫과 나머지가 된다.

이 연산과정은 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