알고리즘은 보아야만 믿을 수 있다.

An algorithm must be seen to be believed.

— 도날드 크누스Donald Knuth (1968)

알고리즘algorithm은 프로그래밍에서 흔하게 접하게 되는 용어입니다. 이 알고리즘이 무엇이냐는 질문에는 문제를 풀기 위한 절차라고 답할 수 있겠지만, 이 이상 명확하게 하기는 쉽지 않습니다. 왜냐면 그것이 정확히 무엇인지 합의된 바가 없기 때문입니다. 따라서 여기선 이를 정의하는 일은 피하려고 합니다.

그 대신, 알고리즘의 특징은 살펴볼 수 있습니다. 알고리즘을 수행하는 가상의 기계를 생각해보면, 얼마나 많은 일이 기계로 불가능한지 알 수 있게 됩니다. 또한 그런 기계가 얼마나 많은 동작을 수행하는지 세봄으로써, 실제 소요 시간을 예측할 수 있습니다.

그러면 간단한 알고리즘으로 시작해 이런 주제들을 하나씩 보도록 하겠습니다.

알고리즘

두 수의 최대 공약수를GCD, greatest common divisor를 구해야 하는 문제가 있다고 해봅시다. 알고리즘이란 이런 문제의 답을 구하는 절차를 일컫습니다. 그리고 대표적인 예시로 기원전에 유클리드Euclid가 소개한 것으로 알려진 유클리드 알고리즘Euclid’s algorithm을 들 수 있습니다.

예를 들어, 두 숫자가 $735$ 와 $315$ 로 주어졌다면, 이 방법은 다음과 같이 최대 공약수를 구합니다.

첫 번째 숫자 $735$ 를 두 번째 수 $315$ 로 나눈 나머지 $105$ 를 구합니다.
나머지가 $0$ 이 아니므로, 두 번째 수 $315$ 와 나머지 $105$ 를 각각 첫 번째와 두 번째 것으로 하고 이 과정을 반복합니다.
나머지가 $0$ 이므로, 나눈 숫자 $105$ 를 최대 공약수로 하고 끝냅니다.

\begin{align*} &\begin{aligned} 735 \bmod 315 &= 105 \\ 315 \bmod 105 &= 0 \end{aligned} \\ \therefore{} &\textrm{GCD}\,(735, 315) = 105 \end{align*}

최대 공약수는 두 수가 공통으로 가진 소수, 즉 공약수를 구해 찾을 수도 있습니다. 여기서는 $735 = 3{\cdot}5{\cdot}7^2$ 이고, $315 = 3^2{\cdot}5{\cdot}7$ 이므로, 방금 구한 것과 똑같은 답으로 $105 = 3{\cdot}5{\cdot}7$ 을 구하게 됩니다. 그런데 유클리드 알고리즘은 이렇게 소수를 찾는 대신 나머지 연산을 이용합니다. 그래서, 나중에 보겠지만, 두 숫자가 커질수록 유클리드 알고리즘이 비교적 더 빠른 방법이 됩니다.

위와 같은 과정은 가상의 프로그래밍 언어로 다음과 같이 표현할 수 있습니다.

유클리드 알고리즘 ( $m$ , $n$ ) // 두 수의 최대 공약수를 리턴

$r \leftarrow$ $m$ 을 $n$ 으로 나눈 나머지

만약

r = 0

이면

리턴

n

아니면

리턴 유클리드 알고리즘(

n

r

)

이 코드는 실제 프로그래밍 코드가 아니지만 이에 가깝게 표현했기 때문에 수도코드pseudocode라고도 부릅니다.

이 알고리즘은 입력 값으로 $m$ 과 $n$ 을 받아, 첫 번째 줄에서 나머지 연산을 하고 그 결과를 $r$ 에 대입합니다. 여기서는 화살표(‘ $\leftarrow$ ’)가 대입의 의미를 나타냅니다.

그 다음, 만약 나머지가 없다면 ( $r=0$ ), $m$ 은 $n$ 으로 나누어 떨어진 것이고, 따라서 $n$ 이 최대 공약수입니다. 이 경우 $n$ 을 결과로 돌려줍니다. (즉 ‘리턴’합니다.)

그렇지 않다면, $n$ 과 $r$ 을 새로운 입력값으로 이 과정을 반복합니다. 여기서 ‘유클리드 알고리즘’이라는 자기 자신을 다시 언급하는데요. 이를 재귀적인recursive 알고리즘이라고 부릅니다.

이처럼 알고리즘이란 기계적으로 따를 수 있는 절차, 또는 특별한 지식 없이 어떤 사람이라도 따를 수 있는 절차라고 할 수 있습니다. 이를 좀 더 구체적으로 정리하자면 이렇습니다.

알고리즘은 유한한 단계로 구성되어야 한다. (즉 무한히 많이 있어선 안 된다.)
각 단계가 여러 방법으로 해석될 여지 없이 명확해야 한다.
펜과 종이만 이용해 (즉 특별한 지식을 필요로 하지 않고) 단계를 따를 수 있어야 한다.

이 기준에 비추어 볼 때, 유클리드 알고리즘은 정말로 알고리즘인 것 같습니다.

하지만 이런 설명이 만족스럽지 않을 수 있습니다. 각 단계가 ‘명확해야 한다’는 것은 어느 정도로 해야할까요? ‘특별한 지식’이 없어야 한다는 것도 어느 정도까지 일까요? 물론 각자가 어느 정도의 기준을 갖고 판단할 수도 있겠지만, 곧 소개할 내용처럼 한 가지 기준을 마련해볼 수도 있습니다.

알고리즘의 구체적인 표현

1900년대 초에는 알고리즘이라는 이름 대신 효과적인 방법effective method이라고 부르곤 했습니다. (여기서 ‘효과적’이란 ‘기계적’이라는 뜻이지만, 번역상 적절한 한국어를 찾지 못했다는 변명을 남겨두겠습니다.) 그리고 다소 불명확한 이 개념을 좀 더 구체화하려는 시도가 여러번 있었는데요.

그 중에 하나는 긴 테이프가 달린 가상의 기계를 떠올린 것이었습니다. 이 기계는 아주 단순해서, 할 수 있는 일이라곤 테이프에 적힌 문자를 하나씩 읽거나 쓰고, 다른 문자를 읽기 위해 테이프를 옆으로 움직이는 것이 전부였습니다.

1930년대에 앨런 튜링Alan Turing이 자동 기계automatic machine라는 이름으로 떠올린 이것은 튜링 머신Turing machine이라고도 불립니다. 또한 계산을 수학적으로 모델링하기 위한 것이기 때문에 계산 모델model of computation의 일종이라고도 합니다.

당시 튜링은 기계로 계산할 수 있는 것을 효과적으로 계산 가능한effectively computable 것이라고 불렀습니다. 중요한 것은, 어떤 기계를 만들더라도, 그 기계로 효과적으로 계산 가능한 것은 튜링 머신으로도 그렇다고 주장한 것입니다. 다시 말해 튜링 머신이 할 수 없는 일은 다른 기계로도 할 수 없다는 것이었습니다.

처치-튜링 명제Church-Turing thesis라고 불리는 이 주장은 아직 반론되지 못한 채로 남아서, 컴퓨터 과학의 기반을 이루는 가설이자 믿음으로 자리잡고 있습니다. 튜링 머신은 앞서 본 것처럼 단순하지만, 이것보다 더 많은 것을 할 수 있는 기계를 여태껏 아무도 생각해내지 못했기 때문입니다.

그러면 이런 튜링 머신이 따르는 절차를 알고리즘이라고 볼 수 있습니다. 간단한 예로, 다음 알고리즘은 ‘안녕’을 읽었을 때 초록 불을, 그렇지 않으면 빨간 불을 켭니다.

글자가 ‘안’이면 다음 글자를 읽는다. 그렇지 않으면 빨간 불을 켠다.
글자가 ‘녕’이면 초록 불을 켠다. 그렇지 않으면 빨간 불을 켠다.

sample turing machine program — 그림 2. ‘안녕’을 읽으면 초록 불을 켜고, 아니면 빨간 불을 켜는 튜링 머신.

그러면 튜링 머신의 단순함 덕분에, 이 절차는 자연스럽게 알고리즘의 특징을 갖게됩니다.

실제로 두 단계 뿐인 유한한 절차만 가집니다.
튜링 머신이 할 수 있는 일은 기껏해야 테이프의 문자를 조작하는 것 뿐이므로, 각 단계는 실제로 명확하게 표현됩니다.
튜링 머신에는 특별히 주입된 지능이라고 할 것이 없습니다. 따라서 실제로 특별한 지식이 필요하지 않습니다.

정리하면, 처치-튜링 명제 덕분에 더 많은 것을 할 수 있는 기계를 찾는 노력이 줄었고, 튜링 머신을 비롯한 계산 모델 덕분에 알고리즘의 구체적인 표현이 가능해졌습니다. 이는 계산 이론theory of computation과 같은 컴퓨터 과학의 분야에서, 기계로 할 수 있는 일이 무엇인지 본격적으로 연구할 수 있는 밑받침이 됐습니다. 그 대표적인 성과로 계산 복잡도computational complexity라는 개념을 통해 알고리즘의 성능을 비교할 수 있는 기준을 마련했다는 것입니다.

계산 복잡도

알고리즘이 풀고자 하는 문제의 답이라면, 이런 질문을 해볼 수 있습니다.

어떤 문제가 있을 때, 이를 풀 수 있는 방법, 즉 알고리즘이 항상 있는가?
있다면, 얼마나 많은 시간과 기억 장치가 필요한가?

여기에는 이미 많은 결과가 나왔고, 정리하자면 이렇습니다.

세상의 모든 문제를 모아놓고 아무거나 골랐을 때, 그것을 푸는 알고리즘이 존재할 확률은 0%이다. (즉 풀 수 없는 문제가 압도적으로 더 많다.)
풀 수 있는 문제 중에서도, 빠르게 풀 수 없어서 사실상 풀기 힘든 문제가 존재한다.
빠르게 풀 수 없는 문제 중에서는, 정말로 빠르게 풀 수 없는 것인지조차 모르는 문제가 존재한다.

따라서 어떻게 보면, 어떤 문제를 빠르게 풀 수 있다는 것은 큰 행운일지도 모릅니다. 그리고 이런 문제는 트랙터블tractable한 문제라고도 불립니다.

problems diagram — 그림 3. 문제들과 풀 수 있는 문제, 트랙터블한 문제 간의 관계.

똑같은 문제에는 여러 알고리즘이 존재할 수 있습니다. 그래서 그중에 더 나은 알고리즘을 가리기 위해, 얼마나 빠르게 풀 수 있는지를 흔히 기준으로 삼기도 합니다.

그런데 여기서 ‘빠르게’ 푼다는 의미를 가다듬을 필요가 있습니다. 알고리즘이 답을 내기 위해 소요되는 시간으로 빠르다는 것을 잰다면, 알고리즘 자체가 느리기 때문인지, 알고리즘을 수행하는 기계가 느리기 때문인지 알기가 어렵습니다. 따라서 기계가 물리적으로 어떻게 만들어졌느냐에 상관 없이, 알고리즘 자체가 요구하는 소요 시간을 어떻게 알 수 있는지가 중요한 문제가 됩니다.

시간 복잡도

알고리즘은 그 단계가 얼마나 많이 수행되느냐에 따라 필요한 시간이 달라진다고 볼 수 있습니다. 따라서 알고리즘의 수행 시간running time, 또는 시간 복잡도time complexity $T$ 를 수행하는 단계의 개수라고 정의해봅시다.

앞에서 언급한 유클리드 알고리즘을, 각 단계에 순번을 매겨 다시 가져옵시다.

유클리드 알고리즘 ( $m$ , $n$ ) // 두 수의 최대 공약수를 리턴

[단계 1] $r \leftarrow$ $m$ 을 $n$ 으로 나눈 나머지

[단계 2] 만약 $r = 0$ 이면

[단계 3] 리턴 $n$

아니면

[단계 4] 리턴 유클리드 알고리즘( $n$ , $r$ )

여기서 입력 값이 $m = 4$ , $n = 2$ 라고 해봅시다. 그러면 총 몇 개의 단계를 거칠까요?

나머지 $r = 0$ 을 얻고 $n = 2$ 를 리턴할 때까지 총 세 단계를 거치게 됩니다. 따라서 $T = 3$ 의 시간 복잡도를 가진다고 할 수 있습니다. (이처럼 $m$ 이 $n$ 의 배수인 경우에 항상 $T = 3$ 이 되는지 확인해보세요.)

이 시간 복잡도는 알고리즘의 소요 시간을 예측하기 위한 도구가 됩니다. 즉 시간 복잡도가 커질 수록, 소요 시간또한 길어질 것으로 예상할 수 있습니다. 실제로도 그런 지 곧 확인해보겠습니다.

시간 복잡도를 결정하는 것들

방금의 유클리드 알고리즘 예시로부터 두 가지 사실을 알 수 있습니다.

다른 입력이 주어지면, 다른 시간 복잡도를 얻게 됩니다. 다시 말해, 시간 복잡도는 입력값에 의존하는 함수입니다.
모든 단계를 똑같이 하나로 셌습니다. 이는 각 단계가 더 이상 나눠서 수행할 수 없는 기본적인 단계라고 암묵적으로 가정한 것입니다.

두 번째 사실은, 시간 복잡도는 그것을 수행하는 계산 모델에도 의존한다는 뜻을 담고 있습니다. 달리 말하면, 어떤 문제를 푸는 알고리즘은, 그 문제 자체가 얼마나 어려운지에 따라서도 시간 복잡도가 달라지지만, 그것을 수행하는 계산 모델이 무엇이냐에도 의존합니다.

사실 이 점은 유클리드 알고리즘을 구체적인 문장으로 표현할 때부터 그대로 나타났습니다. 즉 다음과 같은 단계를 계산 모델이 기본적인 단계로서 수행하기를 바란 것입니다.

[단계 1] $r \leftarrow$ $m$ 을 $n$ 으로 나눈 나머지

다시 말해, 계산 모델에 나머지 연산과 변수 접근이 일종의 내장된 기능으로 있어서 즉각적으로 수행할 수 있다고 가정한 것입니다. 따라서 사실 튜링 머신과는 다른 계산 모델을 가정했던 것입니다. 하지만 이런 목적을 위한 계산 모델은 튜링 머신을 간단히 확장해 만들어낼 수 있습니다.

RAM 계산 모델

변수의 값에 빠르게 접근하는 랜덤 엑세스random access는 튜링 머신으로 불가능합니다. 멀리 떨어진 데이터를 읽으려면 테이프를 일일이 움직여야 하니까요. 따라서 앞서 예로 든 유클리드 알고리즘이 튜링 머신을 위한 것이었다면, 각 단계는 테이프를 어떻게 조작할 것인지로 구성됐을 것이고, 훨씬 더 많은 단계가 필요했을 것입니다.

한편, RAMrandom access machine이라고 불리는 계산 모델은 튜링 머신에 랜덤 엑세스가 있다고 생각한 것입니다. 이것이 지금의 컴퓨터에 좀더 가깝기 때문에 오늘날 알고리즘을 분석할 때 더 흔히 사용됩니다.

하지만 이런 랜덤 엑세스가 가능하더라도, 튜링 머신이 풀 수 없는 문제를 풀 수 있게 되는 것은 아닙니다. 그랬다면, 다른 기계가 풀 수 있다면 튜링 머신도 풀 수 있다고 주장한 처치-튜링 명제를 버려야 했을 것입니다.

정리하자면, 알고리즘의 시간 복잡도를 말하려면 그 전에 계산 모델을 가정해야 합니다. 이것이 알고리즘을 다루는 책에서 시간 복잡도를 설명하기 전에 RAM 모델과 같은 계산 모델을 언급하는 이유가 됩니다.

여기서도 앞으로 이 RAM 모델을 기반으로 알고리즘의 수도코드를 작성할 것입니다. 그러면 본격적으로 유클리드 알고리즘의 시간 복잡도를 구해봅시다.

알고리즘 분석으로 소요 시간 예측하기

앞서 언급한 것처럼, 시간 복잡도는 입력 값에 의존합니다. 그런데 입력 값에 따른 시간 복잡도를 그래프로 그렸을 때, 이것이 반드시 어떤 곡선을 그릴 것이라는 보장은 없습니다.

유클리드 알고리즘 예시에서 봤던 것처럼, 한 쪽이 다른 쪽의 배수가 되는 경우에 시간 복잡도는 $T=3$ 에 불과합니다. 또한 입력 값이 커짐에 따라 시간 복잡도는 불규칙한 패턴을 나타냅니다.

euclid algorithm time complexity — 그림 4. 유클리드 알고리즘의 입력값에 따른 시간 복잡도 예시.

따라서 좀더 제한된 경우의 시간 복잡도를 분석하기 위해, 다음과 같은 특별한 종류의 입력 값에 초점을 둡니다.

최악의 경우worst case: 알고리즘의 시간 복잡도가 가장 커지는 경우
최선의 경우base case: 시간 복잡도가 가장 작아지는 경우
평균의 경우average case: 평균적인 시간 복잡도가 필요한 경우

여기서 주로 관심을 갖게 되는 것은 최악의 경우입니다. 왜냐면 이를 통해 최악의 상황에도 보장되는 소요 시간을 알 수 있기 때문입니다.

함수 표기법

입력값 $n$ 에 따른 시간 복잡도 $T(n)$ 이 있다고 해봅시다. 이런 함수를 분석할 때, $n$ 이 커짐에 따라 함수 $T(n)$ 이 어떻게 변하는지 구하는 것을 어심토틱asymptotic 분석이라고도 합니다. 이때 $T(n)$ 에서 차수가 낮은 항lower-order terms은 관심사가 아닙니다. 이를 위해 틸다tilde(‘ $\sim$ ’)를 이용해 차수가 낮은 항을 버린 근사식을 표현할 수 있습니다.

예를 들어 이렇게 사용합니다.

4n^2 + 5n + 6 \sim 4n^2

좀더 간단한 표현으로 빅오big-O를 사용할 수도 있습니다. 빅오는 함수의 집합이고 $O(f(n))$ 로 표기하는데요. 수학적인 정의가 따로 있지만, $f(n)$ 보다 빠르게 커지지 않는 함수의 집합이라고 대신 설명하겠습니다. 예를 들면 다음이 성립합니다.

\begin{align*} 4n^{2\mathstrut} + 5n + 6 &= O\!\left(n^2\right) \\ 5n + 6 &= O(n) \end{align*}

집합 관계의 표현으로서 ‘ $\in$ ’ 기호를 쓸 수도 있었겠지만 등호(‘ $=$ ’)가 흔히 사용됩니다.

한편, 빅오는 다음 표현도 성립합니다.

4n^2 + 5n + 6 = O(n^{999})

왜냐면 $n^2$ 은 $n^{999}$ 보다 빠르게 커지지 않기 때문입니다.

반대의 것으로 빅오메가big-omega가 있습니다. $g(n) = \Omega(f(n))$ 라는 것은 $g(n)$ 이 적어도 $f(n)$ 만큼은 빠르게 증가한다는 뜻입니다. 예를 들어 이렇습니다.

\begin{align*} 4n^2 + 5n + 6 &= \Omega\!\left(n^2\right) \\ 5n + 6 &= \Omega(n) \\ \end{align*}

한편, $n^2$ 은 $1 \,(=n^0)$ 보다 차수가 크므로 다음 또한 성립합니다.

4n^2 + 5n + 6 = \Omega(1)

만약 $g(n) = O(f(n)) = \Omega(f(n))$ 이라면, 빅세타big-theta로 이 사실을 표현할 수 있습니다.

4n^2 + 5n + 6 = \Theta(n^2)

사람마다 선호하는 표기법이 다를 수 있기 때문에, 자료마다 다른 표기법 사용을 볼 수 있을 것입니다. 개인적인 의견이지만 대체로 선호되는 표기법은 빅세타처럼 쓰이는 빅오인 것 같습니다. 즉 표기는 빅오로 하되 그 실질적인 의미는 빅세타의 것을 따르는 혼동스러운 표기법입니다. 하지만 $O(n^2)$ 에 속하는 함수가 반드시 $n^2$ 항을 가질 필요는 없다는 사실을 기억해야 합니다.

유클리드 알고리즘 분석하기

앞에서 예로 들었던 유클리드 알고리즘의 시간 복잡도를 구해봅시다.

유클리드 알고리즘 ( $m$ , $n$ ) // 두 수의 최대 공약수를 리턴

$r \leftarrow$ $m$ 을 $n$ 으로 나눈 나머지

만약

r = 0

이면

리턴

n

아니면

리턴 유클리드 알고리즘(

n

r

)

최선의 경우는 시간 복잡도가 $\Theta(1)$ 임을 쉽게 알 수 있습니다. 이는 입력 값에 상관 없이 항상 일정한 개수의 단계만 거친다는 뜻이기도 합니다. 실제로, $n=1$ 인 경우를 최선의 경우라고 했을 때, 알고리즘은 세 단계를 거치고 재귀 없이 바로 리턴합니다. 따라서 시간 복잡도 $T(m, n)$ 은 이렇게 구할 수 있습니다.

T(m, 1) = 3 = \Theta(1)

그렇지만 나머지 두 경우는 각각 다른 이유 때문에 구하기가 쉽지 않습니다.

평균의 경우는 무엇이 평균적인 입력 값인지 정하기가 어렵습니다. ( $1$ 부터 $\infty$ 사이에 어느 숫자가 평균적일까요?) 따라서 이 경우는 생략합시다.

최악의 경우는 수학적으로 어렵습니다. 먼저, 유클리드 알고리즘의 시간 복잡도는 다음과 같은 점화식recurrence relation을 갖습니다.

T(m, n) = \begin{cases} T(n, r) + 3 &\textrm{($r > 0$)} \\ 3 &\textrm{($r = 0$)} \end{cases}

이는 $T$ 가 다음과 같이 알고리즘의 재귀 횟수 $k$ 로 결정된다는 뜻입니다.

\tag{Eq.1} T(k) = 3(k+1) = \Theta(k)

즉, 재귀가 수행되지 않으면 $T=3$ 으로 끝나지만, 재귀가 $k$ 번 일어난 뒤에 나머지가 없다면 $T=3(k+1)$ 입니다. 따라서 재귀 횟수 $k$ 가 얼마인지 계산해야 합니다.

한편, 무엇이 최악의 입력 값인지 생각해보면, 피보나치 수Fibonacci number가 나타나게 됩니다. 피보나치 수란 다음과 같이 이전 두 수를 더해 나열한 숫자를 말합니다.

1, 1, 2, 3, 5, 8, 13, 21, \dots

유클리드 알고리즘은 두 수가 연이은 피보나치 수일 때 가장 많이 재귀를 수행하게 됩니다. 이 경우에 다음 재귀의 입력 값이 계속 서로소relatively prime가 되기 때문입니다. 예를 들어, 연이은 피보나치 수 $m = 13$ , $n = 8$ 이 입력으로 주어졌다고 해봅시다. 그러면 유클리드 알고리즘은 다음과 같은 입력 값들로 재귀를 수행합니다.

(m, n) = (13, 8) \rightarrow (8, 5) \rightarrow (5, 3) \rightarrow (3, 2) \rightarrow (2, 1)

이 예시에서 두 가지를 알 수 있습니다.

다음 재귀의 입력 값은 바로 이전의 피보나치 수가 됩니다. 즉, $n$ 번째 피보나치 수를 $f_n$ 이라고 적는다면, 입력 값이 $(f_{n+1}, f_{n}) \rightarrow (f_{n},f_{n-1})$ 로 이어지게 만듭니다.
입력 값 $(f_{n+3}, f_{n+2})$ 은 총 $n$ 번의 재귀를 만듭니다.

사실 피보나치 수는 대략 지수 함수만큼 빠르게 커집니다. 정확히는 황금비golden ratio $\varphi = (\sqrt{5}+1)/2$ 에 대해, $f_{n+2} \sim \varphi^n/\sqrt{5}$ 의 속도로 커집니다. 이로부터 재귀 횟수 $n = \Theta(\lg{f_{n+2}})$ 을 얻습니다.

그런데 로그 값은 숫자가 몇 자리인지 나타내므로, 재귀 횟수는 $f_{n+2}$ 이 몇 자리 숫자인지에 따라 결정이 된다고 결론을 내릴 수 있습니다. 사실 똑같은 결과가 정수론number theory에서 라메의 정리Lamé’s Theorem라는 이름으로 남아있습니다. 이를 참고하면, 입력 값 중 작은 쪽을 $\min(m, n)$ 라고 했을 때, 재귀 횟수는 그 로그에 비례하므로, $\textrm{Eq.1}$ 에서 다음 결과를 얻습니다.

T(m, n) = \Theta(\lg \min(m, n))

이처럼 단순해 보이는 알고리즘도 시간 복잡도 분석이 비교적 까다로울 수 있습니다. 그렇지만 어떻게든 해내서 의미있는 결과를 얻어냈습니다. 그렇다면 이 분석이 정말로 실제 소요 시간을 예측할까요? 직접 알고리즘을 구현해서 시간을 재봄으로써 검증해봅시다.

구현을 통해 분석 검증하기

이제 유클리드 알고리즘을 실제로 구현할 단계입니다. 여기서는 자바Java를 프로그래밍 언어로 선택하겠습니다. 그리고 테스트를 통해 알고리즘이 올바르게 동작하는지 확인하고, 실제로 소요 시간을 측정해보겠습니다.

구현과 테스트

유클리드 알고리즘의 수도코드를 다음과 같이 자바 코드로 옮길 수 있습니다.

public class Euclid {
  static public int getGCD(int m, int n) {
    // handle bad inputs
    if (m <= 0 || n <= 0) {
      return 0;
    }

    int r = m % n;
    if (r == 0) {
      return n;
    }

    return Euclid.getGCD(n, r);
  }
}

여기선 잘못된 입력 값을 처리하기 위한 코드를 맨 위에 추가했습니다. 예외 처리를 위해 다른 방법을 썼을 수도 있겠지만, 여기선 조용히 0을 리턴하는 것으로 대신했습니다. 이를 제외하고는 기존 알고리즘과 같습니다.

이 구현이 원하는대로 동작하는지 확인하기 위해 유닛 테스트unit test를 작성할 수 있습니다. 이를 위해 다음과 같이 JUnit 5 프레임워크를 사용해서, 테스트 케이스를 작성해볼 수 있습니다.

  @Test
  public void testLargeNums() {
    int m = 200000000;
    int n = 100000000;
    int gcd = Euclid.getGCD(m, n);

    assertEquals(100000000, gcd);
  }

이는 실제로 통과하는 테스트 코드입니다.

소요 시간 측정과 시간 복잡도 검증

이제 구현한 알고리즘의 소요 시간을 직접 측정해서, 최악의 경우의 시간 복잡도를 검증해봅시다. 여기선 간단히 일곱 개의 경우에 대해 다음과 같이 구했습니다.

elapsed time plot — 그림 5. 입력 값에 대한 소요 시간. 직선은 회귀선.

위 그래프에서 데이터 사이에 선형적인 관계를 볼 수 있습니다. 가로 축은 로그 스케일이기 때문에, 소요 시간이 $\lg\min(m, n)$ 에 비례합니다.

이로부터, 분석을 통해 구했던 시간 복잡도가 실제 소요 시간과 비슷하다고 결론을 내릴 수 있는데요. 이는 실제 컴퓨터와 가까운 계산 모델인 RAM 모델로부터, 알고리즘에서 시간 복잡도를 적절히 구했다는 의미로 이해할 수 있습니다. 하지만 항상 분석이 실제와 일치하지 않을 수도 있습니다. 왜냐면 실제 컴퓨터는 계산 모델보다 훨씬 더 복잡한 기계이기 때문입니다.

복잡도 클래스

앞서, 유클리드 알고리즘이 최악의 경우에 시간 복잡도로 $\Theta(\lg \min (m, n))$ 을 갖는 것을 보았습니다. 즉 소요 시간이 대략 로그 함수를 따른다고 볼 수 있습니다.

하지만 어떤 알고리즘은 $T(n) = n^2 + 3$ 과 같이 다항 함수polynomial function의 시간 복잡도를 가질 수도 있습니다. 이 경우, 알고리즘이 다항 시간polynomial time을 가진다고도 말합니다.

다시 말해, 시간 복잡도가 $O(n^k)$ 꼴인 것을 다항 시간 알고리즘으로 부를 수 있습니다. 한편, 로그 함수 $\lg n$ 은 다항 함수는 아니지만 $O(n)$ 에 속하기 때문에, 이름에 약간 거짓말이 있는 것 같지만, 유클리드 알고리즘도 다항 시간 알고리즘에 속합니다.

어떤 문제를 다항 시간 알고리즘으로 풀 수 있다면, 그 문제를 $\textsf{P}$ 문제라고 하거나, 복잡도 클래스complexity class $\textsf{P}$ 에 속한다고 합니다. 따라서 최대 공약수를 구하는 문제는 $\textsf{P}$ 에 속합니다. 유클리드 알고리즘이라는 방법을 찾았으니까요.

한편, 어떤 알고리즘이 $T(n) = 2^n + 3$ 처럼 지수 시간을 시간 복잡도로 가지면, 지수 시간exponential time을 가진다고 말합니다. 다시 말해, 시간 복잡도가 $O(2^{f(n)})$ 꼴인 경우입니다. 이렇게 지수 시간 알고리즘으로 풀 수 있는 문제를 모은 클래스를 $\textsf{EXPTIME}$ 이라고도 부릅니다. 한편, 빅오의 정의로 인해, 정의상 $\textsf{P}$ 문제는 모두 $\textsf{EXPTIME}$ 에 속합니다. 즉, $\textsf{P} \sube \textsf{EXPTIME}$ 입니다.

빠르다는 의미

클래스 $\textsf{P}$ 에 속하는 문제를 트랙터블tractable하다고도 부르고, ‘빠르게’ 풀 수 있는 문제를 트랙터블한 문제로 정의하기도 합니다. 반대로 $\textsf{P}$ 에 속하지 않으면 인트랙터블intractable하다고 부릅니다.

다항 시간 알고리즘을 아직 발견하지 못했다고 해서, 그 문제가 트랙터블하지 않다고 결론을 내릴 수가 없습니다. 정말로 다항 시간 알고리즘이 존재하지 않음을 보였을 때, 즉 $\textsf{P}$ 에 속하지 않는다고 보였을 때, 문제가 인트랙터블함을 보인 것입니다. 대표적으로 바둑은 $\textsf{P}$ 가 아닌 $\textsf{EXPTIME}$ 에 속하는 문제로 인트랙터블합니다. 따라서 모든 경우의 수를 조사하는 방법 말고는, 이기는 방법을 ‘빠르게’ 찾아내기란 이론적으로 불가능합니다.

다항 시간 알고리즘이 있는지 아직 모르는 문제도 있습니다. 대표적으로 $\textsf{NP}$ 문제라고 불리는 것들이 그렇습니다. 예를 들어, 다리로 연결된 섬들이 있을 때, 모든 섬을 지나는 경로를 찾는 문제는 소위 해밀턴 경로Hamiltonian path 문제라고 불리는데요. $\textsf{NP}$ 에 속하는 이 문제는 모든 경우의 수를 조사하는 지수 시간 알고리즘 말고는 풀 방법이 아직 없습니다. $\textsf{NP}$ 문제가 $\textsf{P}$ 문제인지 아닌지는 P-NP 문제라는 이름으로 백 만 달러가 걸려있지만 오랜 시간동안 밝혀지지 않았습니다.

따라서 $\textsf{P}$ 문제 외의 것을 마주했다면, 특별한 이유가 없는 한 푸는 시도 자체가 좋은 선택은 아닐 수 있습니다. 튜링 머신이 모든 문제를 풀 수 없듯이, 어떤 문제든 기계로 해결할 수 있다는 가정을 버리고, 트랙터블한 문제에 집중하는 편이 나을 것입니다. 물론 그 특별한 이유를 갖고 미지의 문제에 도전한 덕분에 발전이 생기기도 합니다. 예를 들면, 어떤 수가 소수인지 구별하는 다항 시간 알고리즘을 발견함으로써, 소수 판별 문제가 $\textsf{P}$ 에 속한다고 밝혀진 최근 사례가 그런 것입니다.

사실 $\textsf{P}$ 문제가 이론적으로 중요한 기준점이 되는 이유는, 튜링 머신이든 RAM 이든 동일한 $\textsf{P}$ 문제를 가지기 때문입니다. 다시 말해, RAM 계산 모델이 튜링 머신보다 더 ‘빠르게’ 풀 수 있는 문제는 없습니다. 이는 랜덤 엑세스 자체가, 지수 시간 알고리즘을 다항 시간으로 끌어내릴 수 있는 방법이 아님을 말해줍니다.

한편 실용적으로는, 다항 시간이더라도 대체로 $O(n^2)$ 를 넘어가면 그다지 빠르다고는 생각하지 않는 것 같습니다. 입력 값 $n$ 이 커짐에 따라, 여러 알고리즘의 시간 복잡도 함수 $T(n)$ 이 얼마나 빨리 커지는지 다음과 같이 그려볼 수 있습니다.

various time complexity — 그림 6. 입력 값에 따른 소요 시간 그래프. 로그-로그 스케일. 동일한 소요 시간에 각 시간 복잡도가 얼마나 큰 입력 값을 처리할 수 있는지 보여줍니다. 예를 들어, 지수 시간 알고리즘은 초 단위로 해결할 수 있었더라도 입력 값이 열 배 정도 커지면 금방 일 년 정도가 필요해집니다. 반면, 로그 함수의 경우 백만 배가 커져도 일 분 미만이 소요됩니다.

소요 시간이 시간 복잡도 만큼의 초가 걸린다고 했을 때, 입력 값 $n$ 에 따라 실제로 얼마나 소요 시간이 필요할 지도 볼 수 있습니다. 지수 시간 알고리즘은 입력 값이 열 배 정도 커지면, 분 단위에서 금방 연 단위로 소요 시간이 금방 커집니다. 한편, 로그 함수는 커지는 속도가 비교적 상당히 느립니다.

따라서 유클리드 알고리즘이 빠른 편임을 여기서 확인할 수 있습니다. 반대로, 바둑이나 해밀턴 경로 문제같이 다항 시간 알고리즘이 없는 것들은 입력 값이 조금만 커져도 해결이 현실적으로는 불가능함을 알 수 있습니다.

정리하자면, $\textsf{P}$ 문제는 이론적인 중요도 때문에 강조되곤 합니다. 하지만 알고리즘을 소개하는 자료들이 관심을 가지는 문제들은 주로 $O(n^2)$ 이하의 알고리즘을 갖는 것들이 대부분입니다.

마치며

알고리즘을 분석하기 위해 가상의 기계, 즉 계산 모델을 이용할 수 있었는데요. 여기서는 오늘날 컴퓨터와 가까운 RAM 모델로 유클리드 알고리즘을 분석했습니다. 그리고 시간 복잡도라는 개념으로 소요 시간을 예측해보았고 이를 실제와 비교해보았습니다. 한편, 계산 이론에서 알려진 것처럼, 이런 계산 모델의 한계를 살펴봤는데요. 바둑과 같은 문제를 비롯해 빠르게 풀 수 없는 문제가 존재하고, 나아가 해결 자체가 불가능한 문제가 있음을 언급했습니다.

본문의 자바 코드는 깃허브GitHub에서도 확인할 수 있습니다.

레퍼런스

Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)
Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)
Introduction to the Theory of Computation (3rd ed., Michael Sipser, 2012)
Introduction to Automata Theory, Languages, and Computation (3rd ed., John Hopcroft et al., 2006)
Computational Complexity: A Modern Approach (Sanjeev Arora, Boaz Barak, 2009)
Computers and Intractability: A Guide to the Theory of NP-Completeness (Michael R. Garey, David S. Johnson, 1979)
The Art of Computer Programming, Vol. 1 (3rd ed., Donald Knuth, 1997), 또는 The Art of Computer Programming 1 (한빛미디어, 2006)
The Church-Turing Thesis (Spring 2024 ed., Jack Copeland)
On Computable Numbers, with an Application to the Entscheidungsproblem (Alan Turing, 1937)
Elementary Number Theory (6th ed., Kenneth Rosen, 2011)
PRIMES is P (Manindra Agrawal et al., 2004): 소수 판별 문제의 다항 시간 알고리즘.
Java Microbenchmark Harness (JMH): 자바 코드의 소요 시간 측정에 사용한 도구.