2008학년도 연세대 모의 수리논술(문제일부)

2008학년도 연세대 모의 수리논술(문제일부)

 

 

[문제 2] 

 

컴퓨터를 이용하여 특정한 작업을 수행할 때, 어떻게 컴퓨터에 명령하느냐에 따라 빠른 시간 안에 원하는 정보를 획득하기도 하고 그렇지 못하기도 한다. 시간의 중요성이 빠르게 인식되고 있는 현대사회에서는, 컴퓨터를 효율적으로 이용하여 원하는 정보를 빠른 시간 내에 생산하는 명령체계(알고리즘)를 개발 이용하는 것이 중요한 이슈가 되고 있다. 아래에서는, 임의의 \(n\)개의 서로 다른 숫자 \(a_{1},\,...,\,a_{n}\)이 컴퓨터에 입력되었을 때 이를 증가하는 순서로 정리하는 두 가지의 다른 알고리즘을 소개하고 있다. 

 

(알고리즘 1)

스텝 1. \(a_{1}\)에 새로 이름을 주어 \(b_{1}\)이라고 하자.

스텝 2. \(a_{1},\,...,\,a_{k}\)를 증가하는 순서대로 정리하여 \(b_{1},\,...,\,b_{k}\)라고 부르기로 하자. \(a_{k+1}\)을 이미 정리되어 있는 \(b_{1},\,...,\,b_{k}\)와 비교하여 정리하려고 한다. 이를 위하여 \(a_{k+1}\)을 기존 \(b_{1},\,...,\,b_{k}\)의 작은 숫자부터 차례로 비교하여 \(a_{k+1}\)이 들어가야 할 위치를 알아내고 그 위치에 \(a_{k+1}\)를 집어넣는다. 

스텝 3. 스텝 2를 반복하여 \(a_{1},\,...,\,a_{n}\)이 정리되면, 알고리즘을 종료한다. 

 

(알고리즘 2) 

스텝 1. \(a_{1}\)에 새로 이름을 주어 \(b_{1}\)이라고 하자.

스텝 2. \(a_{1},\,...,\,a_{k}\)를 증가하는 순서대로 정리하여 \(b_{1},\,...,\,b_{k}\)라고 부르기로 하자. \(a_{k+1}\)을 이미 정리되어 있는 \(b_{1},\,...,\,b_{k}\)와 비교하여 정리하려고 한다.

 

스텝 2-A. \(b_{1},\,...,\,b_{k}\) 중 가운데 배치되어 있는 \(b_{[(k+1)/2]}\)와 \(a_{k+1}\)을 비교하여, \(a_{k+1}\)이 \(b_{[(k+1)/2]}\)보다 작으면 \(a_{k+1}\)을 \(b_{[(k+1)/2]}\)의 왼쪽에 배치하고 반대의 경우 오른쪽에 배치한다.

스텝 2-B. \(a_{k+1}\)이 \(b_{l}\)보다 크고 \(b_{l+m+1}\)보다 작다고 하자. 이제 \(a_{k+1}\)을 \(b_{l}\)와 \(b_{l+m+1}\)사이에 배치되어있는 \(b_{l+1},\,...,\,b_{l+m}\)와 비교하여 정리하려고 한다. \(b_{l+1},\,...,\,b_{l+m}\)중 가운데 배치되어 있는 \(b_{l+[(m+1)/2]}\)와 \(a_{k+1}\)을 비교하여, \(a_{k+1}\)이 \(b_{l+[(m+1)/2]}\)보다 작으면 \(a_{k+1}\)을 \(b_{l+[(m+1)/2]}\)의 왼쪽에 배치하고 반대의 경우에는 오른쪽에 배치한다. 

스텝 2-C. 스텝 2-B를 반복하여 \(a_{1},\,...,\,a_{k+1}\)이 정리되면, 스텝 2를 종료한다. 

 

스텝 3. 스텝 2를 반복하여 \(a_{1},\,...,\,a_{n}\)이 정리되면, 알고리즘을 종료한다. 

 

(1) 위 두 알고리즘 중 어느 알고리즘이 우수한지 판단하기 위하여 알고리즘의 성능을 측정하는 지표를 만들고, 지표의 적정성에 관하여 논하시오.

 

(2) (1)에서 제시한 지표를 이용하여 어느 알고리즘이 우수한지 판정하고, 판정근거를 제시하시오. 

 

풀이:

(1) 알고리즘의 성능은 주어진 작업을 빠르게 처리하는가에 달려 있고, 작업처리에 걸리는 시간은 연산의 횟수에 달려 있다. 따라서 두 알고리즘 중 어떤 것이 더 적은 횟수의 연산으로 주어진 작업을 해결할 수 있는가를 판단하면 된다. 

 

만약 특정한 수의 배열이 주어진다면 그것을 처리하는 성능은 각각의 알고리즘에서 연산횟수를 비교하면 된다. 그런데 이 문제에서 요구하는 것은 일반적인 미지의 수 배열이 주어졌을 때 어떤 알고리즘이 우수한가를 판단하는 것이다. 이 경우 연산횟수는 일정한 것이 아니라 입력되는 수의 배열 상태에 따라 달라진다. 

이 상황에서 알고리즘의 우수성은 모든 수 배열의 경우를 고려한 연산횟수의 기댓값으로 판단할 수도 있고 최대 연산횟수로 판단할 수도 있다.

기댓값 기준으로 생각할 때 우수한 알고리즘은 대개의 경우 상대적으로 빨리 작업을 수행하겠지만 때로는 기댓값과 동떨어진 긴 시간이 걸릴 수도 있다. 

반면 최대 연산횟수를 기준으로 한다면 우수한 알고리즘은 언제나 상대적으로 빠른 일정한 시간 내에 작업을 수행한다. 

전자의 경우 전체적으로 과제 수행에 지장을 주는 경우가 발생할 수 있으나 후자는 그런 일이 발생하지 않는다. 

 

이런 특징을 바탕으로 하면 알고리즘의 우수성의 지표는 최대 연산횟수에 의해 판단할 수 있다. 최대 연산횟수가 더 적은 알고리즘이 작업의 효율성과 함께 과제 수행의 안정성과 신뢰성도 보장할 수 있다.

 

(2) (알고리즘 2)는 새로운 수의 위치를 정할 때 이미 정렬된 수가 3개 이상인 어떠한 경우라도 이미 정렬된 3개의 수와 비교하지 않는다. 반면 (알고리즘 1)은 최악의 경우 이미 정렬된 모든 수와 비교해야 한다. 따라서 최대 연산횟수를 기준으로 판단하자면 (알고리즘 2)가 더 우수하다. 

(알고리즘 1)에서 연산횟수가 가장 많은 경우는 새로 정리하려는 수를 이미 정리된 모든 수와 비교해야만 하는 경우이다. 따라서 (알고리즘 1)의 최대 연산횟수를 \(f(n)\)이라고 하면 다음의 식을 얻는다.$$\begin{align*}f(n)&=0+1+2+\cdots+(n-1)\\&=\frac{n(n-1)}{2}\end{align*}$$(알고리즘 2)에서도 연산횟수가 가장 많은 경우는 새로 정리하려는 수를 이미 정리되어 있는 모든 수와 비교해야만 하는 경우이다.

이 상황에서 이미 정렬된 \(b_{1},\,b_{2},\,...,\,b_{k}\)에 \(a_{k+1}\)을 추가로 배열할 때

\(k=2^{m}-1\)(\(m\)은 자연수)이면 가운데 수는 \(b_{2^{m-1}}\)이다. 이때 \(b_{2^{m-1}}\)의 오른쪽과 왼쪽에 각각 \(\displaystyle\frac{k-1}{2}=2^{m-1}-1\)개의 수가 있고 어느 쪽에서 \(a_{k+1}\)을 비교하더라도 최대 연산횟수는 같다. 그 다음 비교에서는 \(2^{m-2}-1\)개의 수에 대해 고려하면 되고, 최대한 \(m\)번 연산하면 된다. 

마찬가지로 \(k=2^{m-1}-1\)일 때 최대 연산횟수는 \(m-1\)외 이다.

그러면 \(2^{m-1}\leq k\leq 2^{m}-1\)일 때 최대 연산횟수는 \(m\)이고$$m-1\leq\log_{2}k\leq\log_{2}(2m-1)<\log_{2}(2m)=1+\log_{2}m\leq m$$이므로 \(m=[log_{2}k]+1\)이고 \(a_{k+1}\)을 추가하면 최대 연산횟수가 \([\log_{2}k]+1\)임을 뜻한다. 따라서 \(a_{1}\)이 주어진 상태에서 \(a_{2},\,a_{3},\,...,\,a_{n}\)을 추가할 때 이를 정렬하기 위한 최대 연산횟수는 각각$$[\log_{2}1]+1,\,[\log_{2}2]+1,\,[\log_{2}3]+1,\,...,\,[\log_{2}(n-1)]+1$$이다. 따라서 \(n\)개의 수를 정렬할 때 최대 연산횟수를 \(g(n)\)이라고 하면 다음의 부등식을 얻는다.$$\begin{align*}g(n)&=\sum_{k=1}^{n-1}{([\log_{2}k]+1)}\\&\leq\sum_{k=1}^{n-1}{\log_{2}k}+n-1\\&\leq\sum_{k=1}^{n-1}{\log_{2}(n-1)}+n-1\\&\leq(n-1)\{\log_{2}(n-1)+1\}\end{align*}$$이때 다음의 부등식이 성립하고$$\frac{g(n)}{f(n)}\leq\frac{\log_{2}(n-1)+1}{\displaystyle\frac{1}{2}n}=\frac{\log_{2}4(n-1)^{2}}{n}=\frac{2\log_{2}(n-1)+2}{n}$$이때 2 이상의 자연수 \(n\)에 대해 \(\displaystyle\frac{g(n)}{f(n)}\)의 값은$$\frac{1}{1},\,\frac{3}{3},\,\frac{5}{6},\,\frac{8}{10},\,\frac{11}{15},\,\frac{14}{21},\,\frac{17}{28},\,...$$이므로 \(\displaystyle\frac{g(n)}{f(n)}\)은 감소수열이고 따라서 (알고리즘 2)의 처리속도가 빠르다는 것을 알 수 있다.