알고리즘과 그 표현

1071과 462의 최대공약수를 구하려 한다. 두 수를 소인수분해하는 방법은 수가 커지면 매우 오래 걸린다. 그런데 "큰 수를 작은 수로 나눈 나머지를 구하고, 작은 수와 그 나머지로 같은 일을 되풀이하다가 나머지가 0이 되면 마지막 나누는 수가 답이다"라는 절차를 따르면 세 번의 나눗셈으로 21을 얻는다. 이 절차를 사람이 아닌 기계가 따르게 하려면 어떻게 적어야 할까? 그리고 절차가 늘 옳은 답을 낸다는 것은 어떻게 확인할까?

2.3.1기계가 따를 수 있는 절차

어떤 문제를 풀기 위해 정해진 순서대로 따르는 명확한 단계들을 알고리즘이라 한다. 알고리즘은 입력과 출력이 정해져 있고, 각 단계가 뜻이 하나로만 해석될 만큼 명확하며, 유한한 단계 안에 반드시 끝나야 한다. "적당히 나눈다"처럼 모호한 지시나, 끝나지 않을 수도 있는 되풀이는 알고리즘이 아니다. 알고리즘은 자연어로 단계를 번호 매겨 적거나, 상자와 화살표로 흐름을 그린 순서도로 나타내거나, 프로그래밍 언어와 비슷한 의사코드로 적는다.

호제법이 옳은 까닭은 \(a = qb + r\)에서 \(a\)와 \(b\)의 공약수는 \(r = a - qb\)도 나누고, \(b\)와 \(r\)의 공약수는 \(a = qb + r\)도 나누기 때문이다. 그래서 두 쌍의 공약수는 모두 같고, 최대공약수도 같다. 반드시 끝나는 까닭은 나머지가 나누는 수보다 작아 매 단계 줄어드는 자연수이고, 자연수는 한없이 줄어들 수 없기 때문이다. 이렇게 알고리즘은 결과가 옳다는 것과 반드시 끝난다는 것을 함께 확인해야 한다.¹

2.3.2어떤 입력에서 틀릴까

알고리즘을 만들 때는 예외적인 입력을 따져야 한다. 예를 들어 여러 수 가운데 가장 큰 수를 찾는 알고리즘을 "최댓값을 0으로 두고, 각 수가 최댓값보다 크면 최댓값을 그 수로 바꾼다"로 적으면, 입력이 모두 음수일 때 0이라는 틀린 답을 낸다. 최댓값의 처음 값을 첫째 수로 두어야 어떤 입력에서도 옳다. 이렇게 빈 입력, 음수, 같은 값이 여러 개인 경우처럼 경계에 있는 입력을 넣어 보는 것이 알고리즘의 오류를 찾는 좋은 방법이다.

2.3.3예제 풀이

알고리즘은 이렇게 적는다. 1단계에서 두 자연수 \(a\), \(b\)를 입력받는다. 2단계에서 \(b = 0\)이면 \(a\)를 출력하고 끝낸다. 3단계에서 \(a\)를 \(b\)로 나눈 나머지 \(r\)를 구한다. 4단계에서 \(a\)를 \(b\)로, \(b\)를 \(r\)로 바꾸고 2단계로 돌아간다. 그림 1처럼 \(\gcd(1071, 462)\)는 세 번의 나눗셈으로 21이다.

\(\gcd(89, 55)\)는 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 0으로 나머지가 이어져 아홉 번의 나눗셈 끝에 1을 얻는다. 89와 55는 이웃한 피보나치 수여서 몫이 매번 1이고 나머지가 가장 천천히 줄어든다. 그래서 두 수가 1000보다 작아도 나눗셈 횟수가 가장 많은 경우가 피보나치 수의 쌍이다. 즉 알고리즘은 입력, 명확한 단계, 출력, 그리고 반드시 끝남을 갖춘 절차이며, 옳은 결과와 끝남을 함께 확인하고 경계의 입력으로 오류를 찾아야 한다.

아래 탐구 카드에서 최대공약수를 구하는 절차를 순서도로 그려 보고, 알고리즘이 어떤 입력에서 틀리는지 찾아보자.

1. 이 방법은 기원전 300년 무렵 유클리드의 『원론』에 실려 있어, 기록으로 남은 가장 오래된 알고리즘 가운데 하나로 꼽힌다. 알고리즘이라는 말은 9세기 페르시아의 수학자 알콰리즈미의 이름에서 왔다.