감히, 알고리즘

0. 감히

나는 컴퓨터공학과를 나오지 않았다. 그리고 그 사실은 내가 프로그래머로 일하는 내내 끊임없이 나를 괴롭혔고, 앞으로도 계속 괴롭힐 예정이다. 정규과정을 마치고 온 사람들에 비해 나는 스스로 기본적인 상식이 부족하다고 스스로 여겼고, 그 차이를 좁히기 위해 나름 더 많이 노력했다. 하지만, 그럼에도 혹시라도 모르는 용어나 알긴 아는데 정확히 이해하지 못하는 용어가 나올때면 이 길이 맞나 하는 박탈감을 느끼게 된다.

어떤 일을 잘 하냐가 용어를 많이 아는 것과 정확히 비례하지 않을것이다. 하지만, 우리는 주변에서 그런모습을 많이 본다. 어떤 단편적인 내용을 잘 모른다는 이유로 사람을 무시하고, 깍아 내린다. 또 자신의 단편적인 지식을 자랑하며, 자신이 특정 분야의 전문가라고 거들먹 거린다. 하지만, 우린 그런 사람들한테 이미 많이 속아왔다.

그러니 이제 그만 속아도 되지 않을까? 어차피 세상에 천재는 몇명 안되고, 우리는 그냥 천재가 만들어 놓은것을 이용할 뿐이라 생각한다. 아니 적어도 나는 그렇다. 천재라고 주장하는 사람은 99.9%로 사기꾼일 가능성이 높다. 이건 통계적으로도 증명할 수 있다. 그러니 겁먹지 말자. 그래서 결국 알고리즘이 있고, 그 알고리즘은 우리같이 평범한 사람들이 천재를 따라할 수 있게하는 시험족보 같은 도구일것이다.

1. 알고리즘이란?

컴퓨터는 한번에 한개만 실행한다. 그러면 한번에 한개만 처리하는 컴퓨터를 위해 우리는 일련의 과정들을 정해 놓는다. 그리고 그 과정이 알고리즘이다.

원카드나 훌라같은 게임을 하면 우리는 본능적으로 카드를 정리한다. 그런게임을 모르더라도 카드를  작은 숫자부터 큰숫자로 정리하려고 할때 우리는 무슨 알고리즘을 쓸까라고 고민하지 않는다. 작은수는 앞으로 보내고, 큰수는 뒤로 보내고, 그후에 어떨때는 작은수부터 정리하고, 어쩔때는 큰수부터 정리한다. 카드를 대충 맞추고, 나중에 한번 싹 정리하기도 하고, 처음부터 칼같이 순서대로 정리하기도 한다.

우리가 쓰는 그 방법들을 컴퓨터에도 비슷하게 시키고, 그 것이 알고리즘이 된다.

2. 알고리즘 Blah Blah

알고리즘을 보다보면 엄청나게 많은 용어가 나온다. 시간복잡도, 공간복잡도, BigO, 최악, 최선, 평균, log , ... 그리고 곧 모르겠다며 포기하게 된다.

나는 감히 말한다. 용어 몰라도 아무 문제 없다. 현업에서 20년넘게 일한 입장에서 자신있게 말할 수 있다. 우리는 천재가 아니다. 적어도 나는 아니다. 속도를 걱정한다면 한번 돌려 보자. 그럼 된다. 최선,최악,평균 같은게 궁금하다면, 여러번 돌려보자. 그럼 알겠지.

3. 퀵소트

알고리즘을 공부하고자 하면 가장먼저 정렬(sort) 를 공부하게 된다. 그리고 퀵소트를 본순간, 당신은 알고리즘의 매력에 빠지게 된다.

정렬이 안된 숫자를 작은수부터 큰수로 정렬하는 정렬 함수를 퀵소트를 이용해서 짜면 다음과 같다.

0. 숫자리스트를 받는다

1. 첫번째 숫자를 기준이라고 하자

2. 두번째숫자부터 마지막숫자까지 돌면서, 첫번째 숫자보자 작은숫자들의 모임과 첫번째 숫자보다 큰 숫자들의 모임을 나눈다.

3. 작은 숫자들의 모임이 1개보다 많으면 퀵정렬함수에 넣어 돌려 받고, 아니면 그냥 쓴다.

4. 3에서 받은 숫자 리스트에 기준숫자를 이어 붙이고,

5. 큰 숫자들의 모임이 1개보다 많으면 퀵정렬함수에 넣어 돌려서 받고, 아니면 그냥 쓴다.

6. 4.에 나온 리스트에, 5.에서 나온 숫자들을 이어 붙인다.

7. 6.에서 나온 숫자 리스트를 돌려준다.

잘 이해가 안되는가? 그럼 [3,2,1,5,4,6] 라는 리스트를 정렬하는 프로그램이라고 해보자

0. [3,2,1,5,4,6] 를 받는다.

1. 기준숫자는 첫번째 숫자인 3이다.

2. 3보다 작은숫자의 모임 [2,1] 과 [5,4,6] 을 얻었다.

3. 작은숫자들의 모임 [2,1]이 1개보다 많기 때문에 퀵소트 프로그램을 돌려서 받는다.

 3.0. [2,1] 를 받는다.

 3.1. 기준숫자는 2이다.

 3.2. 작은숫자 모임은 [1] 이고, 큰숫자모임은 [] 이다.

 3.3. 작은 숫자모임 [1]이 1개보다 많지 않기 때문에 그대로 [1]을 쓴다.

 3.4. [1]에 기준숫자인 2를 붙여서, [1,2] 가 된다.

 3.5. 큰 숫자모임 [] 이 1개보다 많지 않기 때문에 그대로 [] 을 쓴다.

 3.6. 3.4.에서 나온 [1,2]에 3.5.에서 나온 [] 를 뒤에 이어붙이면, [1,2]가 된다.

 3.7. [1,2] 를 돌려준다. (3.은 [1,2]를 돌려 받았다.)

4. 3.에서 나온 [1,2] 에 기준숫자인 3을 이어 붙이면 [1,2,3] 이 된다.

5. 큰 숫자들의 모임 [5,4,6] 이 1개보다 많기 때문에 퀵소트 프로그램을 돌린다.

 5.0. [5,4,6] 을 받는다.

 5.1. 기준숫자는 5이다.

 5.2. 작은숫자 모임은 [4] 이고, 큰숫자모임은 [6] 이다.

 5.3. 작은 숫자모임 [4]이 1개보다 많지 않기 때문에 그대로 [4]을 쓴다.

 5.4. [4]에 기준숫자인 5를 붙여서, [4,5] 가 된다.

 5.5. 큰 숫자모임 [6] 이 1개보다 많지 않기 때문에 그대로 [6] 을 쓴다.

 5.6. 5.4.에서 나온 [4,5]에 5.5.에서 나온 [6] 를 뒤에 이어붙이면, [4,5,6]가 된다.

 5.7. [4,5,6] 를 돌려준다. (5.은 [4,5,6]를 돌려 받았다.)

6. 4.에서 나온 [1,2,3]에 5.에서 나온 [4,5,6] 을 이어 붙이면, [1,2,3,4,5,6] 이 된다.

7. 6.에서 나온 [1,2,3,4,5,6]을 돌려준다.

그래서 이 해당 힘수는 [3,2,1,5,4,6]을 입력으로 받아서 [1,2,3,4,5,6]를 출력한다.