Blog

Blog

알고리즘의 선택과 활용

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

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

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

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

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

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

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

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

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


References

[-] http://ai.cau.ac.kr (Dae-Won Kim)
[1] http://en.wikipedia.org/wiki/Algorithm
[2] http://en.wikipedia.org/wiki/Brute-force_search
[3] http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm
[4] http://en.wikipedia.org/wiki/Quicksort
[5] http://en.wikipedia.org/wiki/Knapsack_problem
[6] http://en.wikipedia.org/wiki/Backtracking
[7] http://en.wikipedia.org/wiki/Branch_and_bound


왜 버전 관리 시스템을 사용해야 할까?

왜 버전 관리 시스템(version control, revision control)을 사용해야 할까? 성공한 프로젝트 개발자에게는 너무나 당연한 명제로 생각 되고 있기 때문에 오히려 왜 사용하지 않으면 안된지를 말하는 것이 쉬울지도 모르겠다. 버전 관리 시스템을 사용해야 하는 이유를 ‘협업’과 ‘변화’에서 찾아야 한다고 생각한다.

소프트웨어 개발에 있어서 항상 일정의 문제와 요구사항의 변화는 개발의 역사와 함께 지금까지도 가장 풀기 어려운 문제로 여겨지고 있다. 일정 관리와 요구사항 변화만 뺀다면 소프트웨어 개발은 지금보다 훨씬 쉬워질지 모른다. 하지만 이 두 가지 사항을 배제한 성공한 프로젝트는 아직까지 없다 라고 확신할 수 있다. 어떤 형태든 고객을 빠르게 만족시켜야 하는 것이 소프트웨어 성공을 결정 짓는 열쇠가 되기 때문이다. 우리는 이런 문제를 해결하는데 있어서 버전관리 시스템을 통해 얻을 수 있는 장점은 다음과 같다.

첫째로, 버전 관리 시스템을 사용함으로써 현재 개발중인 버전과 릴리즈 된 버전을 분리할 수 있다. 같은 소스의 여러 리비전(revision)을 관리할 수도 있다. 리비전을 관리한다는 말은 현재 작업한 버전과 어제 완료하여 출시한 버전으로 따로 구분할 수 있다는 말이다. 이것이 가능함으로써 버전관리 시스템 이전에 우리가 해왔던 일일이 소스를 복사해 보관하고 다른 리비전과 현재 리비전을 수동으로 비교해가며 힘들게 병합(merge) 했던 일들이 손쉽게 해결됐다. 또한 새로운 릴리즈 버전을 준비하면서도 이전 버전의 버그 수정, 적용도 손쉽게 되었다.

두 번째로, history 관리 기능이 강력하다. 공동 작업을 하다 보면 누가 어떤 부분을 수정해 문제가 되었는지 언제 수정되었는지 알 수 없는 경우가 많았다. 다른 사람이 수정한 코드를 제대로 알지 못해서 중복된 코드를 생산해 내거나 알 수 없는 버그를 만들어 내기도 했다. 버전 관리 시스템은 막강한 history기능을 제공함으로써 소스의 추가, 수정, 삭제 등을 모두 추적할 수 있고, 혹시 누가 잘못 수정한 내용이 있다 하더라도 손쉽게 이전으로 돌릴 수 있는 기능을 제공한다.

세 번째로 중앙 집중적 소스관리이다. 버전 관리 시스템 이전에는 개발자 PC에만 존재하는 소스가 있고 여러 가지 이유로 소스가 유실되는 경우도 많았다. 또, 소스 저장소가 여러 군데로 분산되어 있었기 때문에 백업 및 관리하기도 어려웠었다. 개발사에서 가장 큰 자산이 되는 것을 꼽으라면 사람 이외 소스코드를 생각할 수 있을 것이다. 소스코드야 말로 회사가 투자한 결과물의 결정체라고 생각할 수 있다. 이런 결정체를 버전 관리 시스템을 사용함으로써 소스코드를 안전하게 보관할 수 있게 해준다.

국내에는 아직 개발사라고 하면서도 아직 버전 관리 시스템을 사용하지 않는 회사들이 상당히 많은 것으로 알고 있다. 이름만 대면 알만한 회사들도 사용하지 않고 있는 곳도 실제로 알고 있다. 버전 관리 시스템을 도입하는 초기에는 오히려 불편한 것이라고 생각되어 반발이 있을 수 있지만 장기적으로 봤을 때 회사에 분명한 이익을 가져다 줄 것이므로 반드시 도입되어야 한다.

현재 CVS(Concurrent Versioning System)를 시작해서 Subversion, 머큐리얼(Mercurial), Git(분산 버전 관리 시스템) 등 수많은 버전 관리 시스템들이 존재하지만 각각의 장단점이 존재하기 때문에 상황에 맞게 어떤 것을 써도 상관없다. 기능은 약간씩 다르지만 이것들의 공통적인 목표는 ‘협업’과 ‘변화’에 잘 대응하는 개발 환경 구축을 도와주는데 있다. 협업을 통한 일정 통제와 요구사항 변화에 대응에 성공한다면 그 프로젝트는 거의 절반의 성공은 이루고 시작하는 것과 다름 없을 것이다.




Subscribe to: Posts (Atom)