Euclid algorithm

유클리드의 소거법은 알고리즘을 설명하는데 자주 등장합니다.

 

Euclid

 

그 이유 중 하나는 알고리즘(Algorithm)이란 말을 자주 사용하게 된 계기가 되었기 때문일겁니다. 유클리드의 소거법은 두 개의 숫자를 나눌 수 있는 최대 자연수를 찾는 과정을 기술하고 있습니다.

E. 유클리드의 알고리즘 : m과 n이 주어졌을 때, 두 수를 나눌 수 있는 가장 큰 자연수를 찾는다.

E1 : m과 n이 같다면 알고리즘을 종료한다. m이 원하는 답이다.

E2 : m이 n보다 크다면 m ← m-n을 하고 그렇지 않다면 n ← n-m을 한다.

E3 : E1 으로 돌아간다.

 

위의 알고리즘 E를 C 언어 함수로 만들면 아래와 같습니다.

int foo(int m, int n)
{
    while(m != n)
    {
        if( m > n ) m = m-n;
        else n = n-m;
    }
    return m;
}

알고리즘을 제안하면, 가장 중요한 것은 해당 알고리즘이 올바른 해를 보장하는지 검증하는 것입니다. 알고리즘의 무결성 검증은 가장 중요하고, 그 다음으로 효율성 등을 따지게 됩니다. 버그 없는 프로그램 작성의 시작이라고 보시면 됩니다. 요즘은 유닛테스트를 통해서 무결성과 효율성을 테스트해볼 수 있습니다.

 

우리가 원하는 해를 g라 할 때, \(m = ga\) 이고 \(n = gb\)를 만족하며, a와 b는 서로 소인 자연수입니다.

E1에서 m과 n이 서로 같다면, g 는 m이 됩니다.

E2에서 m > n 일 때, m-n = g(a-b) 이고, a-b 와 b 는 서로 소입니다. 서로 소가 아니라면, a-b 와 b는 소인수 p를 공유하고 있어야 합니다. 그런데, 소인수 p를 공유하고 있다면,

a - b = pa' 이라고 할 수 있다.

b = pb' 이므로

a - pb' = pa'

a = p(a'+b')

으로 a 역시 p라는 소인수를 가지게 된다. 이는 가정에 위배되므로 a-b 와 b는 서로 소이다.

 

그러므로 m과 n의 최대공약수는 m-n과 n의 최대공약수와 같다.

m < n 인 경우도 동일하다.

또한 알고리즘은 반드시 유한한 시간 안에 해결되어야 합니다. 물론 무한 같은 유한 시간도 존재합니다.

9자 세 개로 만들 수 있는 가장 큰 수는 얼마인가? 이 문제를 내면 많은 분들이 쉽게 답을 냅니다. 그렇지만, 그 숫자가 과연 얼마나 클 까라는 질문을 던지면, 얼마나 큰지 쉽게 답하지 못합니다. 몇 조? 몇 경? 몇 해? 사실 이것보다 더 큽니다. 아니 우리가 알고 있는 우주에 있는 원소들의 숫자보다도 더 많습니다. 바로 무한같은 유한입니다.

유클리드 알고리즘은 m과 n이 계속 작아집니다. 그러나 m과 n은 항상 1보다 크거나 같습니다. 그러므로 유한한 스텝이 경과하면 m과 n이 같아지게 되어 알고리즘이 끝나게 됩니다.

 

예를 들어서 다음의 알고리즘을 생각해보죠.

F. 주어진 s에 대하여 r*r = s가 되는 해를 찾아라.

F1. r ← 0, m ← s

F2. q ← (r+m) * (r+m)

F3. q = s 라면 이 알고리즘을 끝낸다. 해답은 r+m이다.

F4. q < s 라면 r ← r+m, m ← m/2

F5. F2 로 돌아간다.

 

이 알고리즘은 제곱근을 구하는 방법 중 하나입니다. 그러나 s가 2와 같은 숫자를 주게 되면 이 알고리즘은 무한하게 진행될겁니다. 왜냐하면 2의 제곱근은 이진수 표기법에 의하면 무한소수가 되기 때문입니다.

알고리즘이 갖추어야 하는 요소를 살펴보면 다음과 같습니다.

 

1. 유한성 : 주어진 문제에 대해서 유한한 스텝을 거치면 알고리즘이 종료되어야 한다.

2. 정확성 : 알고리즘의 기술은 정확해야 하며 올바른 결과를 유도해야 한다.

3. 입력 : 알고리즘에는 0개 또는 하나 이상의 입력을 가진다.

4. 출력 : 알고리즘에는 1개 이상의 출력을 가진다.

5. 효율성 : 알고리즘은 효율적이어야 한다. (적어도 현재까지 알려진 바로는)

 

사실 알고리즘이 갖추어야 할 1~4까지 증명할 수 있습니다.

 

제 경우에는 정확성이라는 면을 중요하게 여깁니다. 왜냐하면 대부분의 프로그램에서 버그가 없는 프로그램을 작성해야 하기 때문이죠.

그러나 대부분의 알고리즘에서는 5번 효율성에 대해서 주로 따집니다. 때로는 효율성의 하한을 수학적으로 결정할 수도 있습니다.

예를 들어서 n개의 구슬이 있습니다. 이 중 한 개의 구슬은 정상이 아니라서 다른 구슬과 무게가 다릅니다. 이 구슬들을 천칭저울을 세 번 사용해서 해당 구슬을 찾아내어야 하며, 무게가 가벼운지 무거운지도 알아내야 합니다. 과연 몇 개의 구슬까지 천칭 세 번으로 찾아낼 수 있을까요? (참고로 정상구슬들은 얼마든지 가져다 쓸 수 있습니다.)