한빛출판네트워크

저자: 김대곤

* 알고리즘에 발가락 담그기
* 알고리즘의 Complexity 또는 계산복잡도
* 동적 프로그래밍(Dynamic Programming) – 고급 설계 기법인가?
* Induction과 병합 정렬(Merge Sort) 알고리즘
* 거짓말 같은 Induction

야후 사전에 따르면, Greedy는 ‘욕심사나운/탐욕스러운, 또는 걸신들린/게걸스러운’으로 풀이하고 있다. 그래서 Greedy Algorithm이 탐욕 알고리즘으로 번역되는 듯하다. 필자에겐 Greedy 알고리즘의 속성을 잘 표현하지 못하는 번역으로 보인다. Greedy 알고리즘은 탐욕스러운 알고리즘이라기 보다는 근시안적 알고리즘이다. 근시안적이지만 원하는 결과에 도달할 수 있는 알고리즘이 Greedy 알고리즘이고, 그 반대편에는 지난 기사에서 다룬 동적 프로그래밍이 있다(그럼에도 이 두 가지는 항상 같이 나오면, 매우 유사하다). 즉 동적 프로그래밍은 모든 상황을 고려해서 판단하는 반면에 Greedy 알고리즘은 특정 기준을 가지고 선택한다.

예를 들어, 여러분에 한 장의 지도가 주어져 있다고 하자. 이 지도에는 거리와 등고선이 표시되어 있다. A 도시에서 B 도시로 자동차를 타고 가는데, 기름을 가능한 적게 쓰는 길을 찾는 것이 목적이다. 10% 경사의 오르막 길을 갈 때는 10% 연료를 더 사용하게 되고, 10% 경사의 내리막 길을 갈 때는 10% 연료를 덜 사용한다고 가정하자. 경로 X는 100 km이고 경사는 -10%이고, 경로 Y는 90 km이고 경사가 10%이다. 즉, 경로 X는 90의 연료가 소요되고, 경로 Y는 99의 연료가 소요된다. 필자가 알고리즘을 하나 개발했는데, 그 알고리즘은 경로 Y를 선택한다. 왜냐하면 필자의 알고리즘은 항상 최단거리를 선택하도록 설계되어 있기 때문이다. 하지만 최적의 길은 경로 X이다.

필자는 위에서 필자가 정한 기준을 가지고 경로를 선택했다. 이것이 원하는 결과를 가져다 주는 것과는 무관하게 선택이 이루어졌다. 이러한 접근 방법을 Greedy 전략이라고 부른다. Greedy 알고리즘이란 이러한 Greedy전략이 원하는 결과를 가져오는 경우에 알고리즘에 붙이는 이름이다. 원하는 결과를 가져오지 못한다 하더라도 가끔은 이러한 전략이 사용되기도 한다. 원하는 결과를 얻는데 시간이 너무 많이 걸리는 경우, 정확하게 원하는 결과는 아니지만 그에 가까운 결과를 얻는데 사용하기도 한다.

다시 경로 찾는 문제로 돌아가 보자. 현실적으로 경로 X와 경로 Y가 동시에 존재할 수는 없다. 도시 B의 높이는 정해져 있기 때문에 그러한 두 경로가 존재하는 것은 불가능하다. 더욱 중요한 사실은 경로에 상관없이 경로의 경사의 합은 일정하다. 이러한 가정 하에서 필자의 알고리즘은 최소한의 연료를 쓰는 길을 찾은 것이다. 즉, Greedy 전략에서 Greedy 알고리즘으로 바뀐다.

Greedy 알고리즘은 특정 알고리즘에 붙이는 수식어이기도 하지만, 알고리즘을 설계하는 방법이기도 하다. 먼저, Greedy 전략을 수립하고, 그 전략이 원하는 결과를 주는가 살펴보고, 증명하는 것이다.

생활속에서도 우리는 이러한 알고리즘을 무의식적으로 쓰는데, 고속도로에서 어느 주유소에서 기름을 넣을 것인가 결정할 때 종종 사용한다. 이번에도 주유소의 위치가 표시되어 있는 지도가 주어져 있고, 가장 적은 수의 주유소를 방문하는 것이 목표이라고 생각해보자. 모든 사람들이 가지고 있는 기름으로 갈 수 있는만큼 가고, 다음 주유소까지 갈 기름이 없을 때 그 전 주유소에서 주유를 한다. 지도를 보면서 모든 주유소의 위치를 따지고 있는 사람은 없을 것이다. 다행스럽게도(또는 당연하게) 이러한 전략은 가장 적은 수의 주유소를 방문하게 한다. 어떻게 아는냐고? 증명해 보이라고?

일반적인 증명 방법은 다음과 같다. 누군가가 여러분에게 가장 적게 방문할 경우에 방문하게 되는 주유소의 리스트를 주었다고 생각해 보자. 그 중에 처음 있는 주유소가 출발해서 갈 수 있는 마지막 주유소라면, 여러분의 알고리즘도 그 주유소를 선택했을 것이다. 만약 그렇지 않다면, 그 마지막 주유소 이전에 있는 주유소일 것이다. 왜냐하면 주유하지 않고 마지막 주유소 다음에 있는 주유소에 도착할 수 없기 때문에 반드시 그 전에 주유소를 방문해야 한다. 이 경우에는 주어진 리스트에서 처음 있는 주유소를 빼고, 마지막 주유소를 넣자. 방문해야 하는 주유소의 숫자는 변화가 없다. 계속해서 이런 방식을 취함으로서 여러분이 선택한 주유소로 리스트를 만들 수 있다. 처음 주어진 리스트와 주유소 숫자는 같지만, 여러분이 선택한 주유소로 만든 리스트가 생길 것이다. 즉, 여러분의 리스트도 최소한 방문 수를 주고 있다.

일반적으로 분할 설계(Divide and Conquer), 동적 프로그래밍, 그리고 이번 기사에게 소개한 탐욕 알고리즘이 알고리즘 설계의 3 대 방법이다. 필자는 개인적으로 설계 방법을 4 가지로 분류하는데. 첫째는 상식이고, 둘째는 Induction이다. Induction은 분할 설계의 뼈대를 이루고 있기도 하고 더욱 포괄적이다. 그래서 필자는 Induction에 관한 기사와는 별도로 “Induction과 병합 정렬(Merge Sort) 알고리즘”에서 분할점령과의 Induction 관계를 보여주려고 노력하였다. 나머지는 동적 프로그래밍과 탐욕 알고리즘이다. 그러므로 이번 기사는 알고리즘 설계 기법에 관한 마지막 기사가 될 것이다.