Skip to main content

알고리즘의 선택과 활용

컴퓨터 공학(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

Popular posts from this blog

클라우드 컴퓨팅(Cloud Computing) 기술 정리

1. 클라우드 컴퓨팅(Cloud Computing)이란?

클라우드 컴퓨팅에 대해서는 현재 매우 다양한 정의가 존재한다. 이 중 몇 가지를 정리하면 다음과 같다. 첫 번째 정으로 클라우드 컴퓨팅은 다양한 클라이언트 디바이스에서 필요할 때 언제든지 인터넷을 이용한 공유 풀에 있는 서버, 스토리지, 어플리케이션, 서비스 등과 같은 IT 리소스에 쉽게 접근할 수 있게하는 모델이다.

또 다른 정의로는 서로 다른 물리적 위치에 존재하는 컴퓨터들의 리소스를 가상화 기술로 통합해 제공하는 기술이라고도 생각할 수 있다. 개인적으로 클라우드 컴퓨팅의 개념을 이해는데 세일즈포스닷컴(www.salesforce.com)[1]이 만든 이 동영상[2]이 전반적인 이해를 돕는데 매우 유용하다. 아래 그림은 여러 대표적인 클라우드 서비스들의 사용 예를 보여주고 있다.



1.1. 클라우드 컴퓨팅의 장점[4]

사용자가 자신의 필요에 따라 무한정의 컴퓨팅 자원을 사용할 수 있다는 환상(Illusion)을 제공한다. 그러므로 사용자는 하드웨어와 소프트웨어 시스템을 제공하는 계획을 미리 세울 필요가 없다. 사용자는 작은 시스템으로부터 시작할 수 있고 시스템 자원에 대한 요구가 증가함에 따라 시스템 자원을 증가시키면 된다. 필요에 따라 짧은 시간을 단위로 (예를 들어 프로세서를 시간 당 또는 스토리지를 날짜 당) 사용하고 비용을 지불하면 되고 필요가 사라지면 자원을 더 사용하지 않을 수 있다.

1.2. 기존 클라우드 컴퓨팅 사례1.2.1. 아마존
EC2(컴퓨팅 서비스)Auto Scaling(자동으로 서버 생성 가능)Elastic Load Balancing(소프트웨어 로드벨런싱 기능)CloudWatch(모니터링 정보 제공)Amazon Elastic Block Store(EBS, 빠르고 안정적인 스토리지)Amazon Simple Storage Service(Amazon S3, 스토리지 서비스)SimpleDB(데이터베이스 서비스)
1.2.2. 구글
GFS(구글파일시스템, 대용량 파일 처리 가능 시스템)MapR…

규칙기반 전문가 시스템 (Rule-based expert system)

컴퓨터로 어떤 일을 시킬 때 보통은 명확한 규칙에 따라서 처리하게 된다. 그 이유는 아직 컴퓨터는 인공지능을 갖지 못하였다. 인간처럼 여러 가지 지식과 현상을 조합해 사고하지 못한다는 말이다. 그 때문에 사람이 컴퓨터의 능력을 이용해 어떤 일을 처리할 때는 일련의 규칙이 필요했다. 예를 들면 IF … Then … Else로 표현되는 규칙을 적용하는 것이다.

하지만, 실생활의 문제들은 이것들도 표현할 수 없는 것들이 너무 많다. 인간이 생각하는 거의 모든 것들이 이런 모호함의 집합이다. “오늘 날씨 너무 덥다. 시원하게 에러컨좀 틀어!”라고 했을 때 “너무 덥다.”, “시원하게” 등의 말들은 컴퓨터가 처리할 수 없는 것들이다. 몇 도로 온도를 유지했을 때 시원하다고 느끼는지 컴퓨터 자체만으로는 알 수가 없다. 컴퓨터는 정확히 수치화된 데이터만 가지고 처리하는 기계이기 때문이다. 이런 문제들을 처리하는 여러 방법의 하나인 규칙기반 전문가 시스템(Rule-based expert system)에 대해 얘기해 보겠다.

이처럼 컴퓨터가 처리해야 하는 문제들은 어떤 분야의 전문가가 처리하던 것을 컴퓨터가 대신하는데 의미가 있다. 나는 이것을 전문가의 지식을 처리한다고 정리한다. 그리고 전문가라고 불리는 사람들은 어떤 지식에 대해 규칙을 만들 수 있는 사람이고 규칙이란 앞서 얘기했던 대로 IF … Then … Else 형태로 표현할 수 있는 것을 말한다.

규칙기반 전문가 시스템은 관련주제에 지식이 풍부하고 관련 문제를 푸는데 능숙한 주제 전문가(domain expert), 전문가 시스템을 테스트하고 규칙을 추론할 수 있는 지식공학자(knowledge expert), 전문가 시스템의 개발 리더인 프로젝트 관리자(project manager), 프로그래머(programmer) 그리고 최종사용자(end-user)로 구성되어 있다.

또한, 규칙기반 전문가는 기반지식(knowledge base), 데이터베이스(Database), 추론 엔진(Interface engine), 해설설비…

인터넷이 우리 사회에 미치는 영향

믿기 어렵겠지만 몇 년 전만 해도 간단한 정보를 검색하기 위해선 백과사전이 필요했고 적은 분량의 백과사전에서 찾을 수 없을 땐 도서관에 가야 했고 또 작은 도서관에서 찾을 수 없을 땐 좀더 큰 도서관으로 가야 했었다. 과연 지금의 중학교, 고등학교 학생들은 과연 몇 명이나 이래야만 했던 사정을 이해해줄지 모르겠다.

하지만 이제는 사정이 달라졌다. 인터넷의 등장으로 예전처럼 정보검색에 수많은 시간과 노력을 쏟지 않아도 더 쉽게 더 좋은 자료를 검색할 수 있고 그를 여러 가지 형태의 미디어로 접할 수 있는 시대가 되었다. 예전에 ‘팀 버너스 리(Tim Berners-Lee)’ 가 처음으로 구체적으로 주장했던 하이퍼미디어(Hypermedia)와 그로 이루어진 인터넷으로 인해 우리 생활은 많이 변화했고 또 이제는 없어서는 안될 것으로 멀티미디어 환경으로 진화해 왔다는 사실은 아무도 부인하지 못할 것이다.

사실 인터넷의 등장만으로도 우리에겐 막대한 영향을 끼쳤다. 하지만 여기서 인터넷의 멀티미디어로서의 역할을 배제한다면 그 영향력을 전부 얘기하지는 못할 것이다. 멀티미디어로서의 인터넷은 위에서 얘기한 것처럼 빠른 정보검색은 물론이고 보다 효율적인 방법으로 정보전달의 기능을 가지고 있다.

대학교 1학년 때 처음 컴퓨터를 공부할 때 일이다. 네트웍에 대해 공부하고 있었는데 마침 네트웍을 설명하고 있는 동영상을 인터넷에서 발견했다. ‘The dawn of the Net’ 이라는 동영상 이였는데 네트웍 패킷이나 라우터, 라우터 스위치 등등 전체적인 네트웍에 대해서 알기 쉽게 설명한 동영상이었다. 이 동영상은 너무 쉽고 직관적이어서 누구라도 이것을 본 사람이라면 네트웍에 대해 모두 안 것 같은 착각을 하게 만들 정도였다. 하지만 대략적인 네트웍에 대해서 안다고 해서 전문가가 되었다고 말할 수는 없을 것이다. 간단해 보이는 현상 뒤에 숨겨져 있는 지식들을 모두 이해하고 설명할 수 있을 때 비로소 전문가라 부를 수 있을 것이다.

이런 멀티미디어적인 환경은 대부분에 사람들에게 보다…