알고리즘의 선택과 활용

컴퓨터 공학(Computer Science)에서는 다음과 같은 3가지 기본적인 계층(Layer)으로 구성되어 있다고 말할 수 있다. 수학과 통계 그리고 이를 이용한 알고리즘(Algorithm)¹과 데이터 구조, 그리고 이것들을 가공하여 네트워크(Network), 데이터베이스(Database), 그래픽스(Graphics)를 통해서 표현하는 계층으로 나눌 수 있다. 각 계층은 하위 계층을 바탕으로 상위 계층의 문제들을 풀어갈 수 있다. 때문에 하위 계층일수록 그 역할이 아주 중요하다. 이런 계층 중 수학적 이론에 기반을 두고 이를 통해 실 세계 문제들 풀어갈 수 있는 알고리즘 대해 얘기해보고자 한다.

알고리즘의 목표는 무엇일까? 그것은 어떤 문제를 남들보다 효과적으로 빠르게 해결하고자 하는 것이다. 알고리즘을 잘 만들기 위해서는 잘된 디자인(Design)과 좋은 분석(Analysis)과정이 필요하다. 다시 말해서 어떻게 문제를 풀어나갈지 디자인하는 것과 그것이 다른 방법보다 우수한지 분석할 수 있는 능력이 필요하다는 것이다. 이 과정의 기술은 하루아침에 이루어지는 것이 아니라 어떤 문제가 주어졌을 때 그 문제에 접근(Approach)하는 습관을 꾸준히 길러야만 가능하다.

실제로 많은 개발자들이 프로그램을 만들다 보면 앞으로 증가할 데이터의 양과는 상관없이 현재 테스트 되는 데이터를 가지고 결과가 어느 정도 만족할 수준의 속도라면 그냥 넘어가는 경향이 있다. 10건일 때 결과가 0.1초가 나와서 만족했지만 100만 건 1,000만 건일 때 10시간 100시간 이상이 걸릴 수도 있다. 보통 이런 문제들은 개발 단계에서 나타나기보다는 실제 시스템을 운용할 때 나타나고 그에 따른 손실은 개발 비용과 비교할 수 없을 만큼 크다. 이 때문에 설계 단계부터 알고리즘의 선택은 설계단계부터 아주 신중하게 고려되어야 한다.

아주 간단한 예를 들어 살펴보면 1부터 10까지 숫자가 무작위로 나열되어 있는데 이를 정렬하는 문제를 풀어야 한다고 생각해보자. 모든 문제가 그렇듯이 무한정 시간과 자원이 주어진다고 가정하고 하나씩 정렬하다 보면 언젠가는 답이 나오기 마련이다. 다시 말해 Brute-Force² 방식을 통해 하나하나 모두 나열해 가면 복잡한 디자인 과정 없이도 우리는 이 문제를 풀 수는 있다. 이는 시간복잡도로 표현하면 O(n^2)로 나타낼 수 있다. 작은 양의 데이터의 문제에서는 꽤 좋은 방법이라고 생각될 수도 있겠지만, 대용량 데이터의 문제에서는 그것이 과연 좋은 접근 방법인지는 다시 생각해볼 필요가 있다.

다른 방법으로 큰 집합은 한번에 정렬하기 어려우니 1부터 5까지 그리고 6부터 10까지 나누는 등 작게 쪼개어 부분집합을 정렬하는 방식인 Divide and Conquer³를 생각해볼 수도 있겠다. 결국, 그 유명한 Quick Sort⁴를 적용하는 것이 되는데 위에 Brute-Force 방식보다는 확실히 빨라진다. O(log n) 정보의 시간복잡도가 나올 것으로 예상된다. 하지만, 이것이 최적의 방법일까? 더 나은 방법이 없을지 계속 고민해봐야 한다.

상황에 따라 다르겠지만, 직관적인 방법이 빠를 때도 있다. 10Kg 가방에 넘치지 않게 제한적인 보석을 넣는 0-1 Knapsack⁵ 문제를 생각해 보자. 이 문제를 Brute-Force 방식이나 Divide and Conquer를 이용해 풀기는 어려울 수 있다. 다른 방법으로 현재 취할 수 있는 최선의 결과를 미래에 줄 영향을 고려하지 않은 채 선택하는 Greedy를 생각해 볼 수 있을 것이다. 문제에 따라 Greedy가 위 두 가지 문제보다 훨씬 더 빠른 해답을 줄 수 있다. 하지만, 이 방법이 항상 Global optima 결과를 반환해 줄지는 생각해봐야 한다. 하지만, 이 경우에서 Greedy는 Local optima이라는 문제가 있다.

그럼 Global optima를 구하기 위해서는 어떻게 해야 할까? 0-1 Knapsack 문제에서는 가방에 보석을 담을 수 있는 모든 경우를 생각해보면 Global optima를 구할 수 있다. 트리를 이용해 해당 보석을 담을 경우와 담지 않을 경우를 나누어 모두 탐색하면 최적의 해를 구할 수 있다. 트리를 탐색하다 보면 leaf 노드에 다다랐을 때 잘못된 경로를 통해서 왔는지를 깨 닳은 경우가 있는데 이럴 땐 Backtrack 해 다른 노드를 탐색하게 하는 방법이 Backtracking⁶이다. 또한, 미래의 데이터를 예측해 더는 자식 노드를 탐색하지 않아도 된다고 판단하는 방법이 Branch and Bound⁷ 방법이다.

이 외에 Hill climbing, Genetic algorithm 등등 수많은 많은 알고리즘이 존재한다. 모든 경우를 설명할 수 없지만 잊지 말아야 할 것은 풀어야 할 어떤 문제에 대해서 여러 방법으로 풀 수 있는 경우가 항상 존재하고 그 중에 어떤것이 가장 좋은지 그 솔루션을 분석해 더 좋은 것을 취할 수 있는 선택이 주어진다는 것이다.

어떤 알고리즘을 선택하느냐는 문제의 종류와 프로그램을 사용하는 고객이 원하는 결과 수준에 따라 달라질 수 있다. 하지만, 개발자들은 항상 지금 해결해야 할 문제보다 더 좋은 다른 방법이 있을 수 있다는 것을 인지하고 어떻게 풀어갈지를 설계(Design), 분석(Analysis)해 최적의 방법을 적용할 수 있는 능력을 꾸준히 길러야 할 것이다.

References