<알기쉬운 알고리즘> Chapter2 - 알고리즘을 배우기 위한 준비

2.1 알고리즘 이란 

알고리즘은 문제를 해결하는 단계적 절차 또는 방법이다. 

 

알고리즘의 일반적인 특성 

정확성 : 주어진 입력에 대해 올바를 해를 주어야 한다. 

수행성 : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능 하여야 한다.  

유한성 : 일정한 시간내에 종료되어야 한다. 

효율성 : 효율적일수록 그 가치가 높아진다. 

 

 

2.2 최초의 알고리즘 

가장 오래된 알고리즘은 유클리드(Euclid)의 최대 공약수를 찾는 알고리즘 이다. 

 

유클리드는 2개의 자연수의 최대공약수는 큰수에서 작은 수를 뺀 수와 작은수의 최대공약수와 같다는 성질을 이용하여 최대공약수를 찾았다. 

 

예를 들어, 24와 14의 최대공약수는 24-14=10과 작은수 14와의 최대공약수와 동일하다. 이 과정을 반복하여 최대공약수를 다음과 같이 계산 하였다. 단, 최대공약수 (a,0)=a 이다. 

 

최대공약수(24,14)

=최대공약수(24-14,14) =최대공약수(10,14)

=최대공약수(14-10,10) =최대공약수(4,10)

=최대공약수(10-4,4) =최대공약수(6,4)

=최대공약수(6-4,4) =최대공약수(2,4)

=최대공약수(4-2,2) =최대공약수(2,2)

=최대공약수(2-2,2) =최대공약수(2,0)=2

 

유클리드의 최대 공약수 알고리즘에서 뺄셈 대신에 나눗셈을 사용하면 매우 빠르게 해를 찾는다. 

 

다음은 나눗셈을 이용한 유클리드의 최대공약수 알고리즘이다. 

Euclid(a,b)

입력 : 정수 a,b ; 단 a>=b>=0

출력: 최대공약수 (a,b)

1  if(b=0) return a                                // 두번째 숫자인 b 가 0이면 큰수인 a 를 최대 공약수로 리턴한다. 

2 return Euclid (b, a mod b)                // b 가 0 이 아니면, 작은 수 b 와 a mod b, 즉  a를  b로 나눈 나머지를 가지고 재귀호출 한다. 

 

* 재귀 호출( recursive call) 이란? 

함수 내부에서 함수가 자기 자신을 또 다시 호출하는 행위 끝없이 반복되므로 반드시 함수 내에 재귀 호출 중단 하도록 조건이 변경될 명령문 포함한다.  

 

line 1 에서는  b=14이므로 if-조건이 '거짓'이 된다. 

line 2 에서는 Eucli(14, 24 mod 14) = Euclid(14,10)이 호출 된다. 

 

line 1 에서는  b=10이므로 if-조건이 '거짓'이 된다. 

line 2 에서는 Eucli(10, 14 mod 10) = Euclid(10,4)이 호출 된다. 

 

line 1 에서는  b=4이므로 if-조건이 '거짓'이 된다. 

line 2 에서는 Eucli(4, 10 mod 4) = Euclid(4,2)이 호출 된다. 

 

line 1 에서는  b=2이므로 if-조건이 '거짓'이 된다. 

line 2 에서는 Eucli(2, 4 mod 2) = Euclid(2,0)이 호출 된다. 

 

line 1 에서는  b=0이므로 if-조건이 '참'이 되어, a=2 를 최종적으로 리턴한다. 

 

 

 

2.3 알고리즘의 표현방법 

 

일반적으로 알고리즘은 프로그래밍 언어와 유사한 의사코드(pseudo code)로 표현된다. 이외에도 플로차트(flow chart) 형태로 알고리즘을 표현하기도 하나, 이 역시 매우 제한적으로 사용 된다.

 

 

2.4 알고리즘의 분류 

알고리즘은 문제의 해결 방식에 따라 다음과 같이 분류 된다. 

분할 정복 (Divide-and-Conquer) 알고리즘 

그리디(Greedy) 알고리즘 

동적 계획 ( Dynamic programming ) 알고리즘 **

근사(Approximation) 알고리즘 

백트래킹 (Backtracking) 기법 

분기 한정(Branch-and-Boun) 기법

 

그 외에도 확률 개념이 사용되는 랜덤 알고리즘, 특정 환경에서 제기되는 문제들을 해결하는 병렬 알고리즘, 분산 알고리즘, 양자 알고리즘 등이 있다 . 또한 인공 지능 분야에서 사용되는 유전자 알고리즘 도 있다.

 

해결 방식에 의한 분류 외에도 문제에 기반을 두어 알고리즘을 분류하기도 하는데 그 예로 정렬 알고리즘, 그래프 알고리즘, 기하 알고리즘등을 들 수 있다. 

 

 

 

2.5 알고리즘의 효율성 표현 

알고리즘의 효율성은 알고리즘의 수행 시간 (시간복잡도 : time complexity) 또는 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기 ( 공간복잡도 : space complexity) 라고 한다. 일반적으로 알고리즘들을 비교할 때에는 시간 복잡도가 주로 사용된다. 

 

 

알고리즘의 복잡도를  표현하는데에는 다음과 같은 분석 방법들이 있다. 

최악 경우 분석 (worst case analysis)  : '어떤입력이 주어지더라도 얼마이상을 넘지 않는다. '

평균 경우 분석 (average case analysis) :  입력의 확률 분포를 가정하여 분석, 대부분의 경우 균등 분포(uniform distribution) 를 가정한다. 즉 입력이 무작위로 주어진다고 가정하는 것 

최선 경우 분석 (best case analysis) : 거의 사용 되지 않으나, 최적(optimal) 알고리즘을 고안하는데 참고 자료로서 활용되기도 한다. 

*최적 알고리즘이란 주어진 문제의 하한과 같은 복잡도를 가진 알고리즘을 일컫는다. 즉 최적알고리즘 보다 성능이 우수한 알고리즘은 없다. 

 

일반적으로 최악 경우 분석으로 알고리즘의 복잡도를 나타낸다. 

 

 

예를 들어 철수가 학교에 가는 상황을 생각해보자 

집에서 지하철 역: 6분 

지하철을 타고 학교 역까지 : 20분 (혹시 지하철을 놓치게 되면 다음 열차는 4분 후에 온다.)

역에서 강의 실 까지 : 10분 

이 걸린다고 가정하자 

 

이때 최선 경우는 36분 이다. 

반면 최악의 경우 열차를 놓치게 되면 소요되는 시간은 40분이다. 

평균 시간은 최악과 최선의 중간이라 가정하면 38분이 된다. 

따라서 "늦어도 40분이면 간다." 라고 말하면 이는 최악 경우를 뜻한다. 

 

 

2.6 복잡도의 점근적 표기 

시간(또는 공간) 복잡도는 입력 크기에 대한 함수로 표기하는데, 이 함수는 주로 여러개의 항을 가지는 다항식이다.  그래서 이를 단순한 함수로 표현하기 위해 점근적 표기 (asymptotic notation) 를 사용한다. 이는 입력 크기 n 이 무한대로 커질때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다. 

 

 

O(Big-oh) - 표기 

Ω(Big-Omega)-표기

θ(Theta)-표기

 

O(Big-oh) - 표기는 복잡도의 점근적 상한을 나타내고 Ω(Big-Omega)-표기는 복잡도의 점근적 하한을 나타내며, θ(Theta)-표기는 복잡도의 상한과 하한이 동시에 적용되는 경우를 나타낸다. 

 

 

O(Big-oh) - 표기가 복잡도의 점근적 상한이라는 뜻을 예제를 통해 이해해보자 

복잡도가 f(n)=2n^2-8n+3 이라면, f(n)의 O(Big-oh) - 표기는 O(n^2) 이다. 

먼저 f(n)의 단순화 된 표현은 n^2 이다. 그리고 상한개념을 n이 증가함에 따라 부여하는 과정은  다음과 같다 

 

단순화된 함수 n^2에 임의의 상수 c 를 곱한 cn^2이 n이 증가함에 따라 f(n)의 상한이 된다. 단 c>0. 

 

점근적 상한

 

 

다음의 그래프 처럼 교차점 이후 상한관계를 만족하는 어떤 양수가 존재한다면 f(n)= O(n^2) 으로 표기할 수 있다. 

따라서 O(Big-oh) - 표기에는 c 가 '숨겨져 있다'고 생각 해도 좋다. 

(즉, cg(n)이 n0보다 큰 모든 n에 대해서 항상 f(n) 보다 크다는 것을 보여준다.)

 

복잡도가 f(n)=2n^2-8n+3 이라면, f(n)=  O(n^2) 이며, 

또한 f(n)=  O(n^3),f(n)=  O(2^n) 이다. (n^3, 2^n 각각에 대하여 1과 같거나 큰 양의 상수 c 를 선택하면 늘 성립하기 때문이다. )

 

하지만  

복잡도가 f(n)=2n^2-8n+3 일때, f(n)≠  O(logn),  f(n)≠  O(n),  f(n)≠ O(nlogn)이다.

왜냐하면 O()속의 logn, n, nlogn 각각에 대하여 어떤 양의 상수 c 를 선택하여도  f(n)=2n^2-8n+3 보다 크게 만들수 없기 때문이다. 

 

 

점근적 하한

 

Ω(Big-Omega)-표기가 복잡도의 점근적 하한이라는 뜻을 예제를 통해 이해해보자 

복잡도가 f(n)=2n^2-8n+3 이라면, f(n)의 Ω(Big-Omega)-표기는Ω(n^2) 이다.

( O-표기와, Ω-표기 둘다 복잡도 다항식의 최고 차항만 계수없이 취하면 된다. ) 

 

f(n)=Ω(n^2)는  'n이 증가함에 따라 2n^2-8n+3이  cn^2보다 작을 수 없다'라는 뜻이다.

이때 상수 c=1로 놓으면 된다. '

(즉, cg(n)이 n0보다 큰 모든 n에 대해서 항상 f(n) 보다 작다는 것을 보여준다. ) 

 

 

 

복잡도가 f(n)=2n^2-8n+3 일때, f(n)=Ω(logn),  f(n)=Ω(n),  f(n)=Ω(nlogn)은 각각 성립한다. 

왜냐하면 Ω()속의 logn, n, nlogn 각각에 대하여 어떤 양의 상수 c 를 선택하여  f(n)=2n^2-8n+3 보다 작게 만들수 있기 때문이다. 

 

하지만  

복잡도가 f(n)=2n^2-8n+3 일때, f(n)=  Ω(n^2) 이며, 

또한 f(n)≠Ω(n^3),f(n)≠Ω(2^n) 이다. (n^3, 2^n 각각에 대하여 어떤 상수 c 를 선택하여도  f(n)=2n^2-8n+3보다 작게 만들 수 없기 때문이다. )

 

 

 

θ-표기는 복잡도의 O- 표기와 Ω-표기가 같은 경우에 사용한다. 

따라서  f(n)=2n^2-8n+3 =O(n^2) , f(n)=2n^2-8n+3 =Ω(n^2)이므로 f(n)=θ(n^2)이다.

즉 f(n)은 n이 증가함에 따라 n^2과 동일한 증가율을 가진다는 뜻이다. 

따라서 f(n)≠θ(nlogn), f(n)≠θ(n^3), f(n)≠θ(n),f(n)≠θ(2^n)이다.

 

 

복잡도는 일반적으로 O-표기를 사용하여 표현하며, θ-표기와 혼용하기도 한다. 

 

다음은 컴퓨터 분야에서 시간복잡도를 위해 자주 사용하는 O-표기 들이다. 

O(1)        :상수시간 (constant time)

O(logn)  : 로그(대수)시간 (logarithmatic time)

O(n)       : 선형시간 (linear time)

O(nlogn): 로그 선형시간 (log-linear time)

O(n^2)   : 제곱시간 (quadratic time)

O(n^3)   : 세제곱시간 (cubic time)

O(2^n)   : 지수시간 (exponential time)

 

 

 

2.7  왜 효율적인 알고리즘이 필요한가

 

효율적인 알고리즘은 슈퍼컴퓨터 보다 더 큰 가치가 있다고 말할 수 있다. 즉, 값비싼 하드웨어의 기술 개발 보다 효율적인 알고리즘 개발이 훨 씬 더 경제적이라고 할 수 있다.