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


디자인 패턴(design pattern)은 언제 적용해야 할까?

소프트웨어 설계 시 자주 나는 미래의 변화를 좀더 쉽게 수용하기 위해 지금 당장 디자인 패턴을 적용할 것인지에 대해 고민한다. 프로젝트의 성격과 조직의 특성에 따라 선택의 결과가 때로는 좋았을 수도 그렇지 않았던 경우도 있었다. 그러면 도대체 언제 디자인 패턴을 적용하는 것이 좋을까? 패턴을 적용하는 것이 과연 항상 좋은 결과를 가져다 주는 것일까? 고민에 빠지게 된다.

내가 생각한 결론은 다음과 같다. 디자인 패턴을 적용한 설계가 올바른 설계일 경우도 있고 그렇지 않을 경우도 있다는 것이다. 다음과 같은 3가지 측면에서 생각해 볼 수 있다. 첫 번째로 코드 재사용 측면이다. 디자인 패턴을 적용하게 되면 중복인 코드는 제거되고 코드 재사용 가능한 구조로 바뀌게 된다. 중복된 코드를 제거한다는 것은 그만큼 오류를 줄인다는 것으로 생각할 수도 있다. 결국 많은 부분에서의 코드 커버리지(Code Coverage)를 할 수 있다는 것을 의미한다. 코드 커버리지란 소프트웨어 테스트 시 사용되는 측정 기준 중 하나고, 얼마만큼 그 소프트웨어가 테스트되었는지를 나타낸다. 따라서 코드 커버리지를 증가시킬 수록 그 만큼 테스트가 많이 되었다는 것을 의미한다. 실제로 중복코드와 오류밀도의 관계에 대한 내용이 알려진바 있었다.[1,2]

두 번째는 성능 측면이다. 디자인 패턴을 이용하게 되면 그렇지 않을 때보다 코드는 간결해 지지만 많은 상속(inheritance)과 구현, 컴포지션(composition) 등으로 인해 복잡한 구조를 갖게 될 수 있었다. 이러한 복잡한 구조는 객체 생성에 필요한 오버헤드가 필요하므로 성능저하의 원인이 된다. 실제로 같은 코드를 class와 상속 구조로 만들어 필요할 때마다 새로운 객체를 생성한 코드보다 그렇지 않은 코드가 빠르다는 것을 확인 할 수 있다.[3] 성능이 아주 중요한 소프트웨어라면 복잡한 패턴 적용은 신중히 생각해야 한다.

세 번째는 생산성 측면이다. 디자인 패턴에서 말하는 "확장 가능하고 유지보수하기 수월한" 코드라는 것은 코드 작성시 미래를 염두 해 작성한다는 것을 의미한다. 이는 현재에는 필요 없는 코드라 할지라도 미래에 변경될 것을 예측하여 수정한다는 것을 의미하는데 이것은 엄밀히 따지면 현재 불필요한 일을 하게 되므로 생산성을 저해하게 된다. XP(Extreme Programming)[4] 에서는 생산성 향상을 위해서는 두 번까지의 코드 중복이 일어나기 전까지는 기존 방식을 유지하고 세 번째 중복이 발생할 때 구조를 변경해 보는 것이 생산성 향상에 도움이 된다고 말하고 있다.


References

[1] http://www.wired.com/software/coolapps/news/2004/12/66022
[2] http://www.ibm.com/developerworks/kr/library/tutorial/j-lessismore/section2.html
[3] http://shootout.alioth.debian.org/
[4] http://c2.com/cgi/wiki?ExtremeProgramming


규칙기반 전문가 시스템 (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), 해설설비(explain facilities), 사용자 인터페이스(User interface), 외부 인터페이스(External interface), 개발자 인터페이스(Developer interface), 디버깅 보조도구(Debugging aid)로 구성되어 있다.

규칙기반 전문가 시스템은 특정영역의 문제를 풀기 위한 심벌을 추론할 수 있는 능력을 갖추며 처리 과정과 지식이 분리돼 있다는 특징이 있다. 처리 과정과 지식이 분리되어 있다는 것은 매우 큰 장점이다. 이는 새로운 지식이 추가되었을 때 시스템을 수정하기 쉽게 만든다. 또 규칙기반 전문가 시스템은 해설설비가 있으므로 고전적인 방법과 달리 점화된 규칙을 추적할 수 있으면 이르는 방법을 설명할 수 있다. 간단히 설명해서 어떤 정렬 알고리즘(sort algorithm)은 그것이 어떤 절차를 통해서 정렬되는지 소스코드를 보기 전까지는 알 수 없다. 하지만, 전문가 시스템은 어떻게 결과에 이르렀는지 해설설비를 통해서 가능하다는 얘기이다. 또 불충분하고 완전하지 않은 데이터를 처리할 수 있는 대신 결과에는 항상 실수가 존재할 수 있다.

추론방법의 종류에는 순방향 연결과 역방향 연결이 있다. 순방향 연결을 data driven이라고 하는데 단순히 하나씩 지식을 점화시켜 나감으로써 결과를 찾는 방식이다. 자연스러운 방법이지만 속도가 느린 방법이다. 역방향 연결 방식은 goal driven 방식이라고 불리고 목표를 거꾸로 추론해 나가는 방식이다. 보통은 순방향 연결을 사용하고 그 결과를 검증할 때 역방향 연결을 사용한다.

시스템이 가진 규칙은 보통 겹치지 않게 설정해야 좋지만 불가피하게 상반된 같은 규칙이 공존하는 예도 생길 수 있다. 예를 들면 “더우면 에어컨을 켠다.”라는 규칙과 “더우면 에어컨을 끈다.”라는 규칙이 공존할 수 있다. 상식적으로 두 번째 규칙이 잘못된 것을 직감할 수 있겠지만, 컴퓨터는 이것을 알지 못한다. 이를 해결하기 위해서는 각 규칙에 대해 우선순위(priority)를 정하는 방식이 있다. 전문가가 제안한 규칙은 일반사람이 제안한 규칙보다 우선순위를 높게 측정해 같은 규칙이 충돌되었을 때 먼저 적용하는 식이다. 또 다른 충돌 해결 방법은 최장 일치 전략(longest matching strategy)이라는 방법도 있다. IF … 에 해당하는 규칙 중 더 많은 규칙을 적용하는 쪽을 더 높은 우선순위로 배정하는 방법이다. 결국, 이런 충돌을 잘 해결하기 위해서는 지식에 대한 지식인 메타지식(knowledge about knowledge)이 필요하다.

이처럼 지식기반 시스템은 자연스러운 지식을 표현할 수 있고 통일된 구조를 가지며 지식과 과정이 분리돼 있고 불확실한 지식을 다룰 수 있다는 장점이 있지만, 규칙과의 불분명한 관계를 해석할 수 없고 순방향 연결처럼 비효율적인 탐색전략을 갖는다는 것과 새로운 지식이 추가되었을 때 전문가(사람)의 도움 없이는 스스로 학습할 수 없다는 단점이 있다.

요즘 나는 모호하고 애매한 것을 어떻게 컴퓨터로 풀어나가는지에 대한 내용을 관심 있게 보고 있다. 아직 이것에 대한 지식이 부족해 깊게 얘기할 수는 없지만 결국 인간이 만들어낸 시스템으로 극히 일부 분야에 전문적인 능력을 나타내는 것이 지금 시대가 말하는 인공지능 시스템이라는 것이다. 결국, 터미네이터에서 나오는 skynet이나 인간의 사고를 하는 능력을 갖춘 로봇이 나오기까지는 아직 갈 길이 멀어 보인다. 하지만, 확실한 것은 이것은 하드웨어 분야에서 풀어야 할 숙제가 아니라 결국 소프트웨어 분야에서 풀어야 할 문제라는 것이다. 인간의 두뇌 기억과 사고에 대한 의학적 기술이 발전하고 그것을 소프트웨어로 효과적으로 옮길 수 있는 능력이 발전하는 언젠가 이것은 이루어지리라 생각한다.


References

http://en.wikipedia.org/wiki/Expert_system
http://www.cs.nott.ac.uk/~sxp/ES3/index.htm
http://en.wikipedia.org/wiki/Terminator_3:_Rise_of_the_Machines


생체 정보에서의 보안 대책 필요

정보사회에서는 디지털로 문서가 작성되고 온라인으로 파일(file)이 교환되면서 전자 거래가 증가 하고 있습니다. 특히 인터넷의 등장으로 누구나 쉽게 전자 거래가 가능하지만 오프라인과 똑같은 안전성과 신뢰성을 보장해 주지는 못하고 있고 전자 거래는 신원확인을 할 수 없고 해킹(hacking)의 위험으로 문서의 진위 여부를 판단할 수 없다는 위험이 있습니다. 이를 보완하기 위해 지금까지 많은 기술(VPN, Firewall, PIN: Personal Identification Number 등)이 개발되고 발전되고 있지만 아직 전자서명만큼의 보안성을 제공하지 못하고 있습니다. 전자서명은 신원확인, 위변조 금지, 기밀성 유지, 부인봉쇄 등에 보안환경을 제공하고 있고 전자거래의 법적 효력을 제공하고 있습니다.

전자서명 기술은 첨단정보기술로서 국가의 보안과 경쟁력에 큰 영향을 미치고 있습니다. 전자서명을 이용해 다뤄지는 데이터들이 그만큼 국가 안보에 영향을 미칠 정도의 중요한 것들일 수 있기 때문입니다. 특히 가까운 미래에 그 중요도가 더 높아질 스마트카드, 지문인식, 홍채인식, 얼굴 인식 등의 정보를 다루는 분야에서도 PKI 와의 기술 접목을 고려해서 연구가 진행되어야 한다고 생각합니다.

인간의 생체인식 기술의 경우 의학기술 발전과 더불어 타인의 생체를 이식할 경우 그에 대해 연구는 되고 있지만 실제 적용에 있어 대책이 부족한 실정입니다. 영화 ‘마이너리티 리포트‘를 보면 타인의 홍채를 이식 받아 보안기관의 출입 및 보안정보의 Access까지 가능한 것을 볼 수 있습니다. 비록 영화이지만 이런 대책이 충분히 간구되지 않을 때 아주 실현 불가능 한 얘기도 아닐 것이라 생각합니다.

현재 공개키 기반구조에서의 사용자 인증은 Knowledge Factor(사용자가 알고 있는 것으로 PIN이나 패스워드 등), Possession Factor(사용자가 소유하고 있는 것으로 토큰이나 카드 등), Biometrics Factor(사용자의 유일한 신체적 특징으로 얼굴, 지문, 홍채 등)의 세 가지 방법 중 한 가지 또는 그 이상의 방법을 이용하여 수행될 수 있습니다. Knowledge Factor와 Possession Factor를 사용하는 방법은 현재 가장 많이 쓰이고 있는 방법이지만, 이러한 방법의 단점은 망각 및 유출의 가능성이 있으며, 도난 및 분실에 의한 도용의 위험이 있다는 점입니다. 반면 사용자 인증을 위해 Biometrics factor를 사용하게 되면 소유물이나 현재는 도난, 분실, 위조의 가능성은 낮지만 가까운 미래에 이것들이 보안 위협이 될 수 있습니다.

따라서, 생체 정보와 전자서명이 결합된 정보에 대해 효과적 검증 데이터 생성 방법과 현재 CA들의 생체정보 검증에 대한 기능 확장 및 관련 어플리케이션 개발에 대한 추가 연구가 필요합니다.




Subscribe to: Posts (Atom)