알고리즘(Algorithm)
유한한 단계로 끝나는 명확한 계산 절차. 이름은 9세기 바그다드의 알콰리즈미에서 왔고, 유클리드 호제법(Euclidean algorithm)이 가장 오래된 예로 꼽힌다.
알고리즘은 정해진 입력을 받아, 하나하나가 모호하지 않은 명령을 유한 번 수행하고 멈추어 출력을 내는 계산 절차입니다. 요리법과 닮았지만 '적당히'나 '노릇해질 때까지' 같은 말은 허용되지 않습니다. 누가 따라 해도, 기계가 따라 해도 같은 결과가 나와야 합니다. 이름은 9세기 바그다드의 학자 알콰리즈미에서 왔습니다. 인도식 자리값 기수법으로 계산하는 법을 다룬 그의 책이 라틴어로 옮겨지면서, 그의 이름이 '계산 규칙'을 뜻하는 말이 되었습니다.
가장 오래된 예로 흔히 꼽히는 것은 기원전 300년 무렵 유클리드의 『원론』에 실린 최대공약수(greatest common divisor) 구하기입니다. 큰 수에서 작은 수를 빼도 최대공약수는 그대로이니, 한쪽이 0이 될 때까지 빼기를 되풀이하면 남은 수가 답입니다. 같은 문제를 푸는 알고리즘은 여러 개일 수 있습니다. 빼기를 여러 번 하는 대신 한 번에 나머지를 구하면(나눗셈) 걸음 수가 확 줄어듭니다.
나머지를 쓰는 방법이 가장 오래 걸리는 입력은 이웃한 두 피보나치 수입니다. 몫이 매번 1이라 한 번에 조금씩밖에 줄지 않기 때문입니다. 거꾸로 말하면, 나눗셈을 k번 해야 하는 입력의 작은 수는 적어도 k+1번째 피보나치 수입니다. 피보나치 수는 다섯 항마다 열 배 넘게 커지므로, 걸음 수는 작은 수의 (십진법) 자릿수의 다섯 배를 넘지 않습니다. 1844년 프랑스의 수학자 가브리엘 라메가 증명한 라메의 정리입니다. 지금 입력이라면
무엇이 '명확한 절차'인지를 수학적으로 정한 것은 1930년대의 일입니다. 영국의 튜링은 기호가 적힌 긴 테이프를 한 칸씩 읽고 쓰며 움직이는 가상의 기계, 곧 튜링 기계(Turing machine)로 절차를 정의했습니다. 미국의 논리학자 처치는 함수(function)를 만들고 적용하는 규칙만으로 계산을 적는 람다 계산(lambda calculus)으로 정의했습니다. 둘은 생김새가 전혀 다르지만 계산할 수 있는 것이 똑같았습니다. 이것이 '기계적으로 계산할 수 있는 것은 곧 튜링 기계로 계산할 수 있는 것'이라는 처치–튜링 논제(Church–Turing thesis)의 근거가 되었습니다. 이렇게 정의하고 나면 어떤 알고리즘으로도 풀 수 없는 문제가 있다는 것까지 증명할 수 있습니다. 대표가 프로그램과 입력을 받아 그 프로그램이 언젠가 멈추는지 판정하는 정지 문제(halting problem)입니다.
이어지는 곳. 알고리즘을 설계하는 대표적인 틀이 몇 가지 있습니다. 문제를 같은 모양의 더 작은 문제로 줄이는 재귀(recursion), 반으로 나눠 각각 풀고 합치는 분할 정복(divide and conquer), 겹쳐 나오는 작은 문제의 답을 표에 적어 두고 다시 쓰는 동적 계획법(dynamic programming), 매 순간 가장 좋아 보이는 것을 고르는 욕심쟁이 알고리즘(greedy algorithm), 계산 도중 동전을 던지는 무작위 알고리즘(randomized algorithm)입니다. 가장 많이 연구된 과제는 목록을 크기순으로 늘어놓는 정렬과 목록에서 원하는 것을 찾는 탐색입니다. 알고리즘이 모든 입력에서 맞는 답을 내고 끝난다는 것은 몇 가지 입력을 시험해서는 보일 수 없고, 증명해야 합니다. 반복문마다 깨지지 않는 조건(불변식)과 매번 줄어드는 양을 적어 그 증명을 한 줄씩 해 나가는 방법이 호어 논리(Hoare logic)입니다. 답이 맞는지 확인하기는 쉬운데 빠른 알고리즘이 있는지조차 모르는 문제들을 둘러싼 큰 물음은 P 대 NP 문제(P versus NP problem)입니다. 알고리즘은 정보를 재는 잣대도 됩니다. 프로그래밍 언어를 하나 정해 두면, 어떤 문자열을 출력하는 가장 짧은 프로그램의 길이가 그 문자열의 콜모고로프 복잡도(Kolmogorov complexity)이고, 언어를 바꿔도 이 길이는 문자열과 상관없는 상수만큼만 달라집니다.
이 개념이 나오는 긴 글
이 개념 위에 세워진 것
이 개념을 언급하는 페이지
- 최대공약수와 유클리드 호제법
… 10권은 같은 절차를 길이에 써서 두 길이에 공통 단위가 있는지를 따집니다. 기록으로 남은 가장 오래된알고리즘으로 흔히 꼽힙니다. 베주 항등식이라는 이름은 18세기 프랑스 수학자 에티엔 베주에게서 왔지만, 정수에 …
- 튜링 기계
… 수 없는 문제'가 있음을 보인 것이라, 괴델의 불완전성 정리와 짝을 이루는 결과입니다. 튜링 기계는 '알고리즘'이라는 말에 정확한 뜻을 준 모형 가운데 가장 설득력 있는 것으로 꼽힙니다. 보편 기계 하나를 정해 …
- 처치–튜링 논제
… 형태의 논제는 틀린 셈입니다. 두 물음 모두 아직 열려 있습니다. 이어지는 곳. 이 논제 덕분에 '그런알고리즘은 없다'는 말을 '그런 튜링 기계는 없다'는 정리로 바꿔 증명할 수 있습니다. 계산 모형의 사다리에서 …
- 수학적 귀납법
… 최대공약수는 변하지 않는다는 것이 불변식이고, 나머지가 0이 되어 멈추면 남은 수가 곧 최대공약수입니다(알고리즘). 리스트나 나무처럼 제 안에 같은 모양을 품는 대수적 자료형에서는 같은 원리를 자료의 짜임새를 따라 …
- 점근 표기법
알고리즘이 얼마나 빠른지는 컴퓨터와 언어, 프로그래머의 솜씨에 따라 달라집니다. 그런 것에 흔들리지 않게 …
- 안정 매칭
… 보류로 결정을 미루기 때문에, 한 번 고르면 끝인 욕심쟁이 알고리즘과 달리 늘 안정한 답에 닿는알고리즘입니다.
- 타입 이론
… 데 있습니다. 많은 체계에서 판단이 성립하는지는 기계적으로 가릴 수 있어서, 타입 검사는 반드시 끝나는알고리즘이 됩니다. 늘 그런 것은 아닙니다. 예를 들어 두 항이 같다는 증명을 곧바로 판단의 같음으로 쓰는 …