알고리즘이란

약 2,300년 전에 쓰인 유클리드 『원론』 7권의 최대공약수 구하는 방법은 지금도 컴퓨터 안에서 돌아갑니다.

언제나 통하는 방법

1071과 462를 둘 다 나누어떨어지게 하는 가장 큰 수를 구해야 한다고 해 봅시다. 462부터 1까지 하나씩 나눠 보고 둘 다 나누어떨어지는 첫 수에서 멈출 수도 있습니다. 답은 나오지만 수백 번을 시도해야 할 수도 있습니다. 더 짧은 길이 있습니다. 1071을 462로 나눈 나머지 147을 남깁니다. 이번에는 462를 147로 나눈 나머지 21을 남깁니다. 147을 21로 나누면 나머지가 0이므로 답은 21입니다. 수백 번 대신 나눗셈 세 번이면 됩니다.

이 짧은 길이 알고리즘입니다. 알고리즘은 어떤 입력을 받아 올바른 출력을 내는, 유한한 개수의 정확한 단계 목록입니다. 위의 방법은 최대공약수를 구하는 유클리드 알고리즘으로, 기원전 300년 무렵에 쓰인 『원론』 7권에 나옵니다. 유클리드는 나눗셈 대신 큰 수에서 작은 수를 거듭 빼는 방식으로 설명했지만 생각은 같고, 나머지를 쓰는 방식이 오늘날 프로그램에서 쓰는 형태입니다.

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;   // remainder
    a = b;
    b = r;
  }
  return a;
}
console.log(gcd(1071, 462)); // 21

단계 목록이 알고리즘이 되는 조건

코먼, 레이서슨, 리베스트, 스타인의 교과서 같은 책은 알고리즘을 입력을 출력으로 바꾸는 잘 정의된 절차라고 설명합니다. 이 설명에는 세 가지가 들어 있고, 코드를 쓸 때 하나하나가 중요합니다.

• 정확함. 단계마다 뜻이 하나입니다. 「a를 b로 나누고 나머지를 남긴다」는 정확하지만 「어떻게든 수를 작게 만든다」는 그렇지 않습니다.
• 유한함. 반드시 멈춰야 합니다. 유클리드 알고리즘에서 나머지는 늘 나눈 수보다 작으므로 단계마다 줄어들고, 결국 0에 닿습니다.
• 올바름. 시험해 본 예만이 아니라 허용된 모든 입력에 대해 맞는 답을 냅니다.

요리법이 흔한 예로 쓰이는데, 꽤 맞는 비유입니다. 재료가 입력, 음식이 출력이고 단계에 순서가 있습니다. 차이는 읽는 쪽이 얼마나 채워 넣느냐입니다. 요리사는 「한 꼬집」이 얼마인지 스스로 정합니다. 컴퓨터는 아무것도 정하지 않으므로 컴퓨터용 알고리즘은 모든 단계를 빠짐없이 적습니다.

같은 문제, 다른 알고리즘

문제 하나에는 보통 올바른 알고리즘이 여러 개 있고, 하는 일의 양은 크게 다를 수 있습니다. 1071과 462의 최대공약수를 462부터 하나씩 내려가며 찾으면 21에 닿기까지 442번을 시도해야 하지만, 유클리드 방법은 나눗셈 3번이면 됩니다. 둘 다 맞습니다. 빠른 것은 하나뿐입니다. 이 과정의 상당 부분이 이 두 번째 질문을 다룹니다. 방법이 맞다면, 몇 단계가 걸리고, 입력이 커질 때 그 수가 어떻게 늘어날까요?

이 질문에 답할 때 컴퓨터 과학자는 초 대신 기본 단계(비교 한 번, 교환 한 번, 나눗셈 한 번)를 셉니다. 걸리는 초는 기계에 따라 다르지만, 단계 수는 알고리즘과 입력에만 달려 있어서 두 방법을 공정하게 비교할 수 있습니다. 아래 실험실은 막대를 정렬하면서 비교 횟수를 세어 줍니다. 같은 처음 순서로 두 방법을 돌려 보고 숫자를 비교해 보세요.

입력, 출력, 그 사이의 단계

알고리즘을 쓰기 전에 무엇이 들어가고 무엇이 나와야 하는지부터 정확히 적습니다. 최대공약수라면 입력은 양의 정수 두 개이고, 출력은 둘을 모두 나누어떨어지게 하면서 그보다 큰 수는 그렇지 못한 정수 하나입니다. 이렇게 적어 두면 결과를 어떻게 확인할지 알 수 있고, 단계의 실마리가 보이기도 합니다. 경계에 있는 경우도 드러납니다. 한쪽 수가 0이면 어떻게 될까요? (위의 반복문은 다른 쪽 수를 돌려주는데, 그것이 맞는 답입니다.) 두 수가 같으면 어떨까요? 코드를 돌리기 전에 이런 경우를 생각해 두면 많은 실수를 미리 잡습니다.