알고리즘 강좌 1회

알고리즘 강좌 1회

- 알고리즘 개론 -

 

1. 알고리즘

알고리즘을 한마디로 정의하면,

 

"어떤 문제의 해답을 찾아주는 일반적인 단계별 절차"

 간단한 예를 하나 들어보자. 여러분은 전화번호부에서 사람을 찾을때 어떻게 찾는가?

혹시 전화번호부의 첫장부터 끝장까지 넘겨가면서 원하는 사람의 이름을 찾는가?-_-;; 아마 정상적인 사회생활이 가능한 사람이라면 그런 미친짓은 하지 않으리라 믿는다. 그러면 어떻게 찾는가?

그렇다. 여러분도 아시다시피 전화번호부에 있는 사람들의 이름은 가나다 순으로 정렬이 되어있다. "정동섭"이라는 인물을 찾고자 할 경우 전화번호부의 'ㅈ'항목을 찾은 다음, '정'으로 시작하는 사람들의 이름을 찾고, '동'이라는 글자가 이어지는 이름을 찾아낸 후, 마지막으로 '섭'을 찾으면 "정동섭"이라는 사람의 전화번호를 알 수 있게 되는 것이다. 물론 사람마다 약간의 차이는 있겠지만.

위에서 말한 두가지 방법. 즉 무식한 방법과 유식한(?)방법. 이 두가지 방법 모두다 알고리즘으로 볼 수 있다. "정동섭이라는 이름을 가진 사람의 전화번호 을 찾아라" 라고 하는것이 우리에게 주어진 문제이고, 위에 주절주절 써놓은 것들이 해답을 찾아주는 절차, 즉 알고리즘이다. 그리고 이런 알고리즘을 사용해서 주어진 문제를 해결하는 것을 문제를 푼다(solve)라고 한다.

하지만 전화번호부에서 특정한 사람의 전화번호를 찾는것은 꼭 저 위의 두가지 방법만 있는것은 아니다. 저 두 방법외에 엄청나게 많은 방법이 존재할 수 있다. 이러한 방법들도 모두 알고리즘이라고 할 수 있는 것들이다.

앞으로 이 강좌에서는 여러가지 알고리즘들을 사용해 컴퓨터로 주어진 문제를 푸는 방법에 대에 설명하게 될 것이다. 여러분이 앞으로 공부할 내용들은 모두 이 "알고리즘"에 대한 것들이다.

2. 알고리즘의 중요성

 

앞에서 말했듯이 전화번호부에서 사람을 찾는 방법.. 즉 알고리즘은 여러가지가 있을 수 있다.

하지만 이 중에서 어떤 것을 선택해야 할까? 역시 "유식한 방법"을 선택하는 것이 좋을 것이다. 유식한 방법이 무식한 방법보다 더 빠르기 때문이다.

하지만 앞으로 우리는 이러한 일들을 컴퓨터에게 시킬것이다. 컴퓨터는 연산속력이 인간과는 비교가 안 될 정도로 빠르다. 그러면 컴퓨터는 무지 빠르니까 그냥 무식한 방법으로 풀게 해도 답은 금방 나오지 않을까?

대답은 "No"다. 만약에 찾는 전화번호부에 실린 이름들의 수가 1,000,000,000,000개라고 하자. 찾는 이름이 전화번호부 900,000,000번째에 있다면 컴퓨터는 전화번호부의 이름과 찾고자 하는 사람의 이름을 900,000,000,000번 비교해봐야 할 것이다. 하지만 유식한 방법의 경우 이러한 비교횟수는 크게 줄어든다. 동명이인만 가득한 엉터리 전화번호부가 아니라면 무식한 방법보다는 훨씬 더 빠르게 찾을 수 있을 것이다.

다음 표에서는 1항부터 n항까지 피보나치 수열(Fibonacci Sequence)을 구하는 두 가지 알고리즘이 소요하는 시간을 나타내고 있다. 이 두 가지 방법이 뭔지까지는 알 필요없다.(하지만 이 강좌를 읽는 독자들은 대충 어떤것들인지 감이 오리라 믿는다) 여기서 눈여겨 봐 두어야 할 것은 두 알고리즘이 정답을 출력하는데 소요되는 시간이다.

 

n	유식하게 풀 경우	무식하게 풀 경우
40	41 ns	1048000 ns
60	61 ns	1 초
100	101 ns	13 일
160	160 ns	38000000 년
200	201 ns	40000000000 년

 

여기서 ns는 나노초.. 즉 0.000000001초이다. 위 표에서 볼 수 있듯이, 좋은 알고리즘의 선택은 정답을 한번 보기 위해 40000000000년을 기다리는 불상사를 막아준다.(설마하니 피보나치 수열의 200번째 항을 보고싶어서 40000000000년을 기다리는 사람은 없겠지만) 한마디로 말해서 좋은 알고리즘의 선택이 무엇보다 중요하다는 것이다.

특히나 정보올림피아드 같은 대회를 보면, 모두 하나같이 문제에 제한시간을 두고 있다. "이러저러한 문제를 푸는 프로그램을 작성하라. 단, 프로그램이 10초이내에 답을 출력해야 한다." 프로그램으로 하여금 복잡한 문제를 풀때 빠른 시간내에 답을 출력하게 하려면 역시 "좋은 알고리즘"을 사용해야한다.

3. 시간복잡도

 

시간복잡도.. 영어로는 time complexity.

시간복잡도란 알고리즘의 수행속도에 대해 프로그램,컴퓨터,언어 등등의 세부사항과는 독립적인 측정법이다.

일반적으로 알고리즘의 수행시간은 입력데이터의 크기(위의 예를 보면 피보나치 수열의 항수)에 따라 증가하고, 컴퓨터가 실행하는 연산이 몇 번이나 수행되는가에 비례한다. 알고리즘 중의 일정한 명령문들을 선택해서 단위연산으로 잡고, 이 단위연산을 몇 번 수행하는가 알아내는 것이 시간복잡도를 분석하는 것이다.

내가 써놓고도 무슨말인지 모르겠군. 예를 들어보자.

for i:=1 to n do begin

for j:=1 to n do begin

...어쩌구 저쩌구 처리...

end;

end;

이런 프로그램에서, 가운데에 어쩌구 저쩌구 처리.. 하는 부분을 단위연산이라고 생각해보자. 이 어쩌구 저쩌구 처리는 이 프로그램을 다 끝냈을때 몇 번 수행될까?

당연히 n*n=n2 번이 될 것이다. 어쩌구 저쩌구 처리가 엄청 긴 명령문들이든, 엄청 짧은

명령문이든 상관없이 n2번 이 명령문들을 실행하게 된다. 이 경우의 시간복잡도는 n2 이라고 말할 수 있다.

그런데 다음과 같은 경우는?

for i:=1 to n do begin

for j:=i to n do begin

...단위연산...

end;

end;

이경우 단위연산을 수행하는 횟수는... 1+2+3+4+...+n 이므로 계산하면 (n2+n)/2 이다.(수1 교과서에 나와있다-_-;) 이때의 시간복잡도도 역시 단위연산의 수행횟수, 즉 (n2+n)/2이다.

하지만 이렇게 시간복잡도를 말해버리면 좀 멋이 없어보인다. 그래서 그랬는지 몰라도 전산학자들은 O표기법이란 것을 만들었다. 사실 O표기법의 정의에 대해 파고들어가면 끝이 없으므로, 여기서는 간단히 생각하기로 한다. 시간복잡도에서 나온 식에서 가장높은 차수만을 써주면 되는 것이다.

즉 시간복잡도 (n2+n)/2는 O(n2) 로 표시한다. 최고차항 앞에 붙어있는 계수도 생략한다. 고로 시간복잡도가 100n이어도 O(n), 0.1n이어도 O(n)이 되는 셈이다. 이렇게 계수를 생략해 버리는 이유는 "별로 중요하지 않기때문"이다. 500n과 0.1n2를 생각해 보자. 언뜻 보기에는 500n쪽이 더 수행시간이 느리지만, 조금만 n이 커지면 형세는 금방 역전된다. 즉 계수보다는 차수가 더 수행시간에 영향을 준다는 소리다.

결국, 시간복잡도가 O(n2)라는 말은 "이 알고리즘의 수행시간은 n2에 비례한다!" 라는 말의 다른 표현이 되는것이다.

이런 식으로 거의 모든 알고리즘들의 시간복잡도를 나타낼 수 있다.

O(n), O(n2), O(n4), O(n100), O(log n), O(nlog n), O(2n)

이런 식으로 알고리즘의 시간복잡도를 표현하면, 알고리즘들의 수행시간들을 대충 짐작할 수 있게 된다. n의 최대크기가 100일때 O(2n)의 알고리즘으로 답을 구한다고 생각해 보자. n이 100이면 컴퓨터는 2100번의 단위연산을 수행해야 된다. "음, 내가 살아있는 동안 답을 보기는 힘들겠구나"라고 생각하면 될 것이다.

알고리즘의 시간복잡도를 분석할 수 있으면, 자신이 선택한 알고리즘이 수행되는 시간을 대충이나마 짐작할 수 있다. 이렇게 되면 자신이 어떤 알고리즘을 선택해서 문제를 풀어야 될 지 명확하게 알 수 있을 것이다.