알고리즘과 자료구조 1강. 요리법과 알고리즘의 차이
소금 약간이라고 적힌 요리법은 알고리즘이 아닙니다. 둘을 가르는 것은 해석의 여지를 한 톨도 남기지 않겠다는 각오입니다.
풀고 시작
소금 약간이라고 쓰는 순간
할머니의 김치찌개 요리법에는 이런 문장이 있습니다. "간이 맞을 때까지 소금을 넣으세요." 사람은 이 문장을 읽고 멀쩡히 요리를 해냅니다. 그런데 같은 문장을 기계에 넘기면 기계는 첫 줄에서 얼어붙습니다. 얼마나 넣으라는 것인지, 언제 그만두라는 것인지 판정할 방법이 없기 때문입니다. 도널드 커누스는 알고리즘이 갖춰야 할 조건을 다섯 가지로 정리했습니다. 반드시 유한한 단계 안에 끝나야 하고(유한성), 각 단계가 애매함 없이 규정되어야 하며(명확성), 정해진 형태의 입력과 출력이 있어야 하고, 각 단계는 사람이 종이와 연필로도 수행할 만큼 기본적이어야 합니다(유효성). "소금 약간"은 명확성을 어기고 "간이 맞을 때까지"는 유한성을 보장하지 못합니다. 알고리즘이 요리법보다 대단해서 구별되는 것이 아닙니다. 실행하는 쪽이 상식도 눈치도 없다고 가정하고 쓰였느냐가 다를 뿐이죠. 참고로 이 단어 자체가 9세기 바그다드 학자의 이름에서 왔다는 사연은 단어의 유래 편에 있습니다.
같은 답을 내는데 값이 다릅니다
1071과 462의 최대공약수를 구해 봅시다. 학교에서 배운 방법은 두 수를 소인수분해한 뒤 공통 인수를 곱하는 것입니다. 답은 21이고 딱히 어렵지 않습니다. 문제는 수가 커질 때 벌어집니다. 소인수분해는 수가 커질수록 급격히 버거워지거든요. 유클리드가 원론에 적어 둔 방법은 발상이 전혀 다릅니다. 큰 수를 작은 수로 나눈 나머지로 작은 수를 갈아 끼우는 일을 나머지가 0이 될 때까지 반복하기만 합니다. 1071을 462로 나누면 나머지가 147, 462를 147로 나누면 나머지가 21, 147을 21로 나누면 나머지가 0이므로 답은 21입니다. 단 세 번이면 끝나죠. 두 방법은 같은 답을 내지만 비용이 자라는 방식이 다릅니다. 시행 나눗셈은 수의 크기에 끌려가고, 유클리드 호제법은 자릿수 규모에 끌려갑니다. 300자리 수를 집어넣는 순간 한쪽은 여전히 순식간이고 다른 쪽은 사실상 불가능해집니다. 알고리즘 공부의 절반은 답이 같은 두 절차 사이에 숨은 이 격차를 알아보는 눈을 기르는 일입니다.
편집기를 열기 전에 종이를 펴세요
문제를 받았을 때 가장 흔한 실수는 곧장 코드를 치기 시작하는 것입니다. 파이썬이냐 자바냐를 정하는 순간부터 세미콜론과 들여쓰기와 씨름이 시작되고, 정작 풀어야 할 논리는 뒤로 밀려납니다. 그래서 알고리즘을 다루는 사람들은 의사코드(pseudocode)로 먼저 씁니다. 실행되지는 않지만 사람이 읽으면 무슨 일이 일어나는지 정확히 알 수 있게 쓴 절차 기술이죠. 호제법을 의사코드로 옮기면 "b가 0이 아닌 동안, a와 b를 각각 b와 a를 b로 나눈 나머지로 바꾼다"가 전부입니다. 파이썬에서는 a, b = b, a % b 한 줄이고 C에서는 임시 변수를 하나 두어야 하지만, 그 줄이 무엇을 하는지는 언어와 아무 상관이 없습니다. 의사코드로 걸러 내고 나면 남는 것은 단계와 조건과 반복이라는 세 개의 뼈대뿐입니다. 언어는 그 뼈대에 입히는 옷일 뿐이죠.
맞다고 어떻게 장담합니까
몇 번 돌려 보고 답이 맞으면 된 것 아닐까요. 다익스트라의 유명한 한마디가 여기에 답합니다. 테스트는 버그가 있다는 것을 보여 줄 수는 있어도 버그가 없다는 것은 결코 보여 주지 못합니다. 가능한 입력은 무한한데 시험해 본 입력은 늘 유한하기 때문입니다. 그래서 알고리즘의 정확성은 확인의 대상이 아니라 증명의 대상입니다. 가장 널리 쓰이는 도구가 루프 불변식(loop invariant), 반복이 도는 내내 참으로 유지되는 명제입니다. 증명은 세 지점을 봅니다. 첫 반복에 들어가기 전에 그 명제가 참인지(초기), 한 바퀴 돌고 나서도 여전히 참인지(유지), 반복이 끝나는 순간 그 명제가 우리가 원하던 결론으로 바뀌는지(종료)를 따지죠. 호제법의 불변식은 "지금의 a와 b의 최대공약수는 처음 두 수의 최대공약수와 같다"입니다. 나머지 연산이 이 값을 보존하니 유지되고, b는 매 반복마다 반드시 작아지니 언젠가 0에 닿아 종료합니다. b가 0일 때 최대공약수는 a이므로 답도 맞습니다. 유한성과 정확성이 한 번에 증명된 셈이죠. 다음 강에서는 이 눈으로 정렬과 탐색을 들여다봅니다.
인출 문제
생각해볼 질문 (정답 없음)
- 사람이 따르는 절차 중에는 "적당히", "느낌껏"이라는 여백이 있어야만 잘 굴러가는 것들이 있습니다. 그 여백을 전부 없애 알고리즘으로 바꾸면 우리는 무엇을 얻고 무엇을 잃게 될까요.
이전: 컴퓨터의 원리 4강 · 다음: 알고리즘과 자료구조 2강