CUBE iwork8 Ultimate 윈도우즈 타블렛 개봉기

요즘 중국에 Intel Atom칩이 싸게 확 풀렸나 보다. 중국에서 폰 좀 만든다는 업체들이 $100 이하의 폰과 타블렛을 하루가 멀다하고 내놓고 있다.

원래 Windows를 별로 좋아하지 않지만, 그래서 회사 PC도 리눅스를 쓰지만, 안드로이드가 좀 지겹더라.

게다가 Windows 8 이후로 소개된 메트로UI가 은근히 편하고 취향에 맞더라. 그래서 언젠가 적당한 가격의 Windows 타블렛이 나오면 지르리라 마음먹고 있었다.

Hadoop.3 Hadoop 생태계 Zoo

By J2eeDev.org

지난 시간에 우리는 Hadoop 스택의 아랫쪽 기반(HDFS, YARN)에 대해 살펴 보았다.

이제 그 위에 있는 몇가지 것들에 대해 살펴볼 차례이다. 이것들은 짧은 시간이지만 급격하게 진화해 왔다. 그래서 우리는 이것들의 역사와 맥락에 대해 알아볼 필요가 있다.

이 상위 모듈들은 우스꽝스러운 이름들이 붙어 있어서 그 정체를 한눈에 파악하기 어렵다.  대부분 동물과 연관된 이름들이기 때문에 이런 모듈들을 묶어서 동물원(Zoo)라고도 한다.

Apache MINA로 간단한 HTTP 서버 만들기

나는 주로 Java로 시스템 프로그래밍을 한다. 시스템 프로그래밍은 대부분 외부 시스템과의 통신을 필요로 하고 따라서 네트워크 프로그래밍을 많이 한다. 

C에서 socket 프로그래밍을 하다가 Java로 넘어온 나로서, 오리지널 Java의 스트림 기반의 네트워크 프로그래밍은 매우 생경했다. 그런데 Java 2에서 NIO(Non-blocking I/O)가 소개되면서 그나마 좀 편해졌다.

NIO는 socket 프로그래밍을 현대적으로 계승한 것 같은 API 세트를 가지고 있기 때문이다.

Hadoop.2 HDFS와 YARN

이 글에서는 HDFS와 YARN에 대해서 한발짝 더 들어가 보기로 한다.

HDFS는 Hadoop Distributed File System의 약자로 여러 서버에 걸쳐 분산된 형태로 파일을 저장하기 때문에 확장성이 있고 이동이 용이한 파일 시스템이다. 이는 Java로 개발되었으며 Hadoop 프레임워크의 가장 아랫단에서 인프라 역할을 한다.

파일시스템은 흔히 우리가 얘기하는 NTFS, EXT4, FAT 이런 것들을 연상하면 된다. 이들 기존의 파일시스템들은 한 서버 내의 물리적 디스크를 조직하는 것이었다면...

Hadoop은 여러 서버에 걸쳐 있는 분산된 저장 리소스들을 논리적으로 하나로 엮은 상위 레벨의 파일시스템이라 볼 수 있다. 물론 각 서버 내에서는 그 서버의 OS에서 사용하는 NTFS나 EXT4 같은 물리적 파일시스템을 활용한다.

Kodu.1 컴퓨팅적 사고 / 코두(Kodu) 설치하기

요즘 정부에서 소프트웨어 교육을 강화한다고 설레발을 치고 있다. 그런데 사실 이런 움직임은 필요하다. 선진국이라는 곳에서는 이미 초등학교부터 프로그래밍 교육을 하고 있다.

아니 정확히 말하면 "Computational Thinking"을 교육하고 있다. 우리말로는 "컴퓨팅적 사고思考"라고 하는데 영 어색하다. 컴퓨팅적 사고는 교육의 측면에서 정의한 용어이기 때문에 그를 설명한 문서를 보더라도 영 감이 잡히지 않는다.

프로그래머로 20년 밥벌이 한 경험에 비추어 볼 때, 컴퓨팅적 사고는 아이들에게 논리적으로 생각하는 법을 가르치는 것이라 추측된다.

어떤 사람이 프로그래머로서의 자질이 있나 없나를 판단할 때는 그 사람에게 어떤 문제를 주었을 때 그 해결 방법에 대해 절차를 논리적으로 잘 설명하는지를 보면 된다. 물론 개중에는 구글링 잘하고 Ctrl-C/Ctrl-V를 잘하는 것이 자질이라고 생각하는 사람도 있을 것이다. (나도 물론 많이 그런다)

Hadoop.1 Hadoop 스택 개요

By Timo Elliott

이 시리즈는 Coursera의 Hadoop Platform and Application Framework 강의를 듣고, 내용을 요약 정리한 것이다. 

지금까지 빅데이터의 기술적인 면과 비지니스적인 면에 대해 기본적인 개념을 훑어 보았다. 이제부터는 기술적인 면에 집중해서 특히 Hadoop 스택이 어떻게 생겼고, 어떻게 동작하고, 이것으로 무엇을 할 수 있는지 알아볼 것이다.

먼저 Hadoop에 대해 간단히 설명하면 "안정적이고, 확장성 있고, 분산 컴퓨팅을 지원하며, 저렴한(commodity) 서버들로 클러스터를 구성하여 커다란 데이터 집합들을 배치하고 분산 프로세싱을 가능케 하는 오픈소스 소프트웨어"이다.

BigData.9 Hadoop 설치하고 둘러보기

By Cloudera

이 글에서는 Hadoop이 어떤 것인지 맛보기 위한 가장 쉬운 방법을 소개할 것이다.

먼저 Hadoop이 뭔지 정의를 살펴보자.  Apache Hadoop 프로젝트는 안정적이고, 스케일러블하고, 분산 컴퓨팅을 지원하기 위한 오픈소스 소프트웨어를 개발하고자 하는 것으로, 일반적인(commodity) 서버들의 클러스터에 커다란 데이터 집합들을 배치하여 분산 프로세싱을 가능케 한다.

그렇다면 왜 사람들은 Hadoop에 열광하는 것일까? 그것은 적은 비용으로, 확장성이 뛰어나며, 무장애로 운영할 수 있으며, 유연하기 때문이다.

Blogger에서 소스코드를 예쁘게 - Syntax Highlighter

By Iwan Gabovltch

원래 소스코드는 알록달록해야 제 맛이다. 그리고 가변폭이 아니라 고정폭 폰트로 스타일링 되어야 코드답다.

개발과 관련된 블로그이다 보니, 소스코드를 자주 넣어야 하는데 그때마다 Syntax Highlighter가 아쉽곤 했다. Wordpress라면 플러그인 형태로 제공되는 다양한 선택사항이 있지만, 여기는 Google Blogger이니 직접 손으로 때워야 한다.

Google Blogger에서도 Syntax Highlighter를 사용할 수 있는 옵션들은 몇개 있다. 그 중에서 하나를 고르기 위해 다음과 같은 기준을 세웠다. 이 기준은 귀차니즈머의 취향이 99% 반영된 것이다.

BigData.8 데이터 과학자들을 분석해 보면?

By O'Reilly

여기서는 오아일리 미디어(O'Reilly Media)에서 발간한 "분석가를 분석하다(Analyzing the Analyzers - Harlen D. Harris, Sean Patrick Murphy, Marck Vaisman)"라는 보고서의 내용을 소개할까 한다. 

이 보고서는 데이터 과학자들이 스스로를 어떻게 생각하는지, 그리고 그들의 일에 대해 어떻게 생각하는지를 설문조사하여 정리한 것이다. 그들의 경력이나, 학위, 사용하는 도구, 직위, 연봉, 조직 같은 것들은 고려하지 않았다. 단지 그들이 가지고 있는 기술이 무엇인지를 알고 싶었던 것이다.

소셜 네트워크를 통해 온라인 설문조사를 했으며, 완료된 설문 개수는 250개 였다.

BigData.7 데이터 과학자가 갖추어야 할 소양

By Pixabay

지금까지 알아 보았듯이 데이터는 넘쳐나는데, 이것을 다룰 수 있는 재능있는 사람은 찾기 힘들다.

맥킨지(McKinsey Global Institute)의 "Big Data Report"에 의하면...

2018년까지 미국에서만 심층 분석 기술(deep analytical skill)을 가진 인력은 14만~19만 정도 부족하고, 빅데이터 분석을 활용하여 효율적인 의사결정을 할 수 있는 관리자와 분석가가 150만명이 부족하다고 한다.

좀 뻥이 심한 것 같기는 하지만 그런 경향이라는 건 부정할 수 없다.

빅데이터와 머신러닝에 대한 즐겨찾기 모음

By Pixabay

요즘 빅데이터(big data)와 머신러닝(machine learning)에 대해 열공 중입니다.

늦은 나이에 굉장히 부담되는 공부지만, 고마운 분들이 좋은 자료를 만들어 두셔서 그나마 조금씩 감을 잡아가고 있습니다.

산재되어 있는 여러 관련 정보들을 모아 두었으니, 같은 주제로 고민하고 계시는 분들께 작은 도움이 되었으면 합니다.

이 페이지는 계속 업데이트될 예정입니다.

Life is not earning but learning.
- Sunil Joyia

BigData.6 데이터 과학자는 뭐하는 사람일까?

실제 빅데이터의 가치는 무엇일까?

고객으로부터 만들어지는 혹은 정보 시스템에서 만들어지는 대량의 데이터를 계산하여, 정확한 예측 모델을 만들고 이를 통해 데이터 기반의 의사결정을 하고자 하는 것이다.

요즘의 컴퓨터 시스템은 더 이상 결정론적인(deterministic) 기계가 아니다. 요즘 정보 시스템들은 손에 잡히는 곳에 있지 않고 멀리 클라우드(cloud)에 혹은 가상 세계에 존재한다.

데이터 과학자(data scientist)는 빅데이터로부터 원료를 공급받는다. 데이터 과학자들은 이 새로운 빅데이터로부터 도전을 받고, 자극을 받고, 영감을 얻게 된다.

BigData.5 성공적인 빅데이터 프로젝트의 조건

지금까지 빅데이터의 다양한 측면을 살펴 보았다.

왜 데이터가 많아질 수 밖에 없는지, 빅데이터의 잠재력은 무엇인지, 빅데이터와 사물인터넷이 어떤 관계가 있는지, 빅데이터의 분석과 예측을 통해 얻은 통찰이 왜 유용한지 등이다.

이제 빅데이터 혹은 작은 데이터 프로젝트가 성공하기 위해 필요한 조건들을 살펴보자.

BigData.4 하이프 사이클로 본 빅데이터

By Jeremy Kemp, Wikipedia

Gartner가 해마다 발표하는 신기술의 하이프 사이클(Hype Cycle for Emerging Technologies)에 대해 알고 있는가?

하이프 사이클은 "과대 광고 주기"라고 직역되기도 하는데, 한마디로 어떤 기술이라는 것이 세상에 나오게 되면 기술 촉발(technology trigger) - 부풀려진 기대의 정점(Peak of Inflated Expectations) - 환멸(Trough of Disillusionment) - 계몽(Slope of Enlightenment) - 생산성 안정(Plateau of Productivity)이라는 다섯 단계를 거치게 된다는 것이다.

BigData.3 Hadoop의 개요

앞서 Hadoop에 대해 살짝 맛을 보았듯이, Hadoop은 데이터와 프로세싱을 모두 담당하는 구조이다.

데이터 측면에서는 HDFS(Hadoop Distributed File System)를 통해 분산 파일 시스템을 구현했고, 프로세싱 측면에서는 MapReduce 프로그래밍 모델을 사용한다. MapReduce는 아주 큰 데이터를 분산하여 처리하는데 적합하다.

BigData.2 급변하는 빅데이터 스택

여기서는 활발하게 기술이 개발되고 제품이 쏟아져 나오는(emerging) 빅데이터 스택에 대해서 얘기해 본다.

여기서 스택(stack)이라고 하는 것은 계층별로 다른 기술들이 중첩된(쌓여있는) 모양을 이야기 하는데, 예를 들어 프로토콜 스택이라고 하면 OSI 7레이어처럼 각 계층마다 다른 기술들이 독립적으로 쓰일 수 있는 모양을 의미한다. 빅데이터에서도 계층별로 다양한 기술들이 쏟아져 나오고 있기 때문에 스택으로 생각하면 편하다.

BigData.1 빅데이터가 대체 뭐냐?

소프트웨어 엔지니어 더 정확히 말하면 프로그래머의 수명은 몇 살까지일까? 외국에는 백발의 할아버지 프로그래머들도 활동한다지만, 우리나라는 40대 중반 정도가 평균인 것 같다. 그런데 내가 벌써 40대 중반을 넘어갔다. 

처음 프로그래밍에 대해 열정적으로 빠져들었을 때, 참 많은 것을 짧은 시간에 배운 것 같다.  그렇게 한번 불꽃처럼 타오른 뒤 , 그 열정은 서서히 식어가고 있었다. 20년 동안 젊을 때 익혔던 기술과 지식으로 잘 버텨왔는데, 어느새 세상이 확 바뀌어 버리고 말았다. 

몇년 전부터 빅데이터, Hadoop, Map-Reduce, Machine Learning, Deep Learning 등의 듣도보도 못한 용어들이 튀어나오기 시작하더니, 예전에는 구현되기 어려울 것이라 생각했던 지능적이고 고도화된 서비스들이 튀어나오기 시작했다. 그리고 이들 서비스들을 제공하는 업체들이 세계를 지배하게 되었다.

LG G4와 루나폰 카메라 화질 비교

나는 최신 스마트폰에 둔감한 편이다. 내가 스마트폰을 고르는 기준은 1등 제품이 아닐 것(그래야 다 같이 먹고 살 것 아닌가?), 가성비가 뛰어날 것, 튼튼할 것, 되도록 작을 것, 그리고 절대적인 가격이 쌀 것. 이 정도이다.

그래서 전에는 팬텍의 VEGA 아이언을 사서 만족스럽게 잘 쓰고 있었다. 그런데 언젠가 아들놈이 가지고 놀다가 떨어뜨리는 바람에 액정이 깨지고 말았다.  액정 수리비를 알아보니 15만원 정도... 이 정도면 그냥 새거 사겠다 싶어서 깨진 상태에서 버텼다.

그러나 와이프가 폰을 바꾼다길래 따라 갔다가, 얼떨결에 나도 폰을 장만해 버렸다. 순전히 우발적인 상황이었다.

헐렁한 유로플러그(Europlug) 안전하게 사용하기

사람들은 메이드인 차이나라 그러면 업신여기는 경향이 있지만, 요즘 웬만한 제조물품들은 중국도 꽤나 잘 만든다. 아니 샤오미나 팍스콘을 보면 꽤나 잘 만드는 정도가 아니라 아주 잘 만든다.

중국이 세계의 공장이 되면서 미국도 그렇고, 우리나라도 그렇고 제조업의 경쟁력이 많이 떨어졌다. 그래서 간혹 보면 꼭 필요한 물건인데 우리나라에서는 팔지 않거나 아주 비싸게 팔리는 것들이 있다.

Wireshark 리눅스에서 No Interface 문제 해결하기

Wireshark는 이더넷 인터페이스 카드를 통해 드나드는 데이터들을 캡쳐할 수 있는 요긴한 프로그램이다.  나같이 프로토콜을 구현하고 테스트하고 연동하는 사람에게 이 툴은 권총처럼 옆에 항상 차고 다닌다고 보면 된다.

Wireshark이 네트워크 카드의 데이터 흐름을 캡쳐할 수 있는 이유는 드라이버 레벨에서 동작하는 모듈이 있기 때문이다.  Windows 용 Wireshark는 WinPcap 모듈을 이용하고,  리눅스에서는  dumpcap 이라는 데몬을 사용한다.

그런데 리눅스의 dumpcap은 그냥 설치하는 것 만으로는 동작하지 않는다.  네트워크 카드에서 정보를 추출하는 것은 뭔가 해킹과 같은 늬앙스를 풍기기 때문에, 리눅스에서는 권한을 부여받은 어플리케이션만 네트워크를 캡쳐할 수 있도록 제한하고 있기 때문이다. 

30장 : 오토마타(Automata)와 XML 파서

강의의 마지막입니다.  마지막을 무엇으로 할까 고민하다가 "오토마타(Automata)"를 골랐습니다. 

오토마타는 상태(State) 집합과 상태간의 전이(Transition)를 모델링한 것으로 이들이 하나의 시스템을 이루면 "유한상태 기계(Finite-State Machine)"라고 합니다.

실로 현실의 많은 것들이 이 오토마타로 표현될 수 있습니다만 가장 대표적으로 쓰이는 분야가 논리적으로 구성된 프로그래밍 언어를 해석하는 파서(Parser) 분야입니다.  현재 개발할 때 사용하는 C++, Java 등의 언어들은 더 낮은 레벨의 언어로 변환되어야 하는데,  고레벨 언어를 해석하는 역할을 오토마타가 맡고 있습니다.

이 장에서는 오토마타의 기본적인 개념을 살펴 보고, 오토마타를 활용한 예로서 XML 문서를 해석하는 XML 파서를 만들어 보도록 하겠습니다.

29장 : 알고리즘 개발 방법론 2 (Greedy Method, Backtracking)

알고리즘 개발 방법론 두번째 장으로 욕심쟁이 기법(탐욕, Greedy Method)와 백트래킹(Backtracking)에 대해서 알아봅니다.

사실 이 두가지 기법은 모든 방법을 동원해서도 풀리지 않는 문제가 있을 때, 마지막으로 시도해볼 수 있는 방법입니다.  혹은 문제의 최적화된 해법을 구하기 전에 미리 그 해답을 찾는 방법이기도 합니다.

그런 의미에서 매우 중요하고 알아두어야 할 기법입니다. 그런데 그 내용을 들여다 보면 우리가 흔히 하는 작업들에 대해 체계적으로 정리해 놓은 것에 불과하다는 생각이 듭니다.

28장 : 알고리즘 개발 방법론 1 (Divide and Conquer, Dynamic Programming)

지금까지 살펴 본 알고리즘들은 주어진 문제를 최적으로 해결하는 것들이었습니다.  우리의 선조들이 힘든 연구와 통찰을 통해 찾아낸 아름답고도 멋진 해법들입니다.

하지만 이들은 처음 접한 문제들에 대해 어떻게 해법을 찾을 수 있었을까요? 또 우리가 새로운 문제를 접하게 될 때, 참조할 만한 비슷한 연구 결과가 없다면 어떻게 해결해야 할까요?

"알고리즘 개발 방법론"이라는 소제목으로 소개시켜드리고자 하는 네가지 접근법은 바로 이렇게 특별한 최적화된 해법이 없는 문제에 대해 어떻게 접근하여 최적화된 혹은 쓸만한 해법을 찾을 수 있는지에 대한 "방법론"을 살펴볼 것입니다.

27장 : 회귀와 스플라인 (Regression & Spline)

이번 장에서 배우는 회귀(Regression)과 스플라인(Spline)은 다른 큰 학문 분야의 맛보기로 제시한 것입니다.

회귀는 통계학의 기본이 되는 개념으로, 실제 측정된 데이터로부터 일반화된 수식을 얻어내는 기법을 의미합니다.  측정된 데이터가 많을 수록 더 정확한 수식을 얻어낼 수 있으며, 이 수식을 바탕으로 미래에 일어날 사건을 예측할 수 있다는 점에서 "통계 학습(Statistical Learning)"의 출발점이라 볼 수 있습니다.

통계 학습은 요즘 뜨고 있는 빅데이터 분석과도 밀접한 관계를 가지고 있습니다.

스플라인(Spline)은 몇몇 제어점을 이용하여 부드러운 곡선을 만들어내는 수학적 도구입니다.  회귀와 비슷한 개념을 기하학적으로 바라보는 관점입니다.

26장 : 수치 미적분

미분(Differential)과 적분(Integral)의 개념이 창안되고 나서 수학의 세계는 혁명적인 변화를 경험하게 됩니다.

현재 상태만을 주시하던 인간들은 상태의 변화를 볼 수 있게 되었고, 더 나아가 상태 변화의 변화까지 볼 수 있게 되었습니다.  비유하자면 심봉사가 눈을 뜬 것과도 같은 인식의 지평이 열린 대 사건입니다.

대학에 들어가서 배우게 되는 거의 모든 분야의 공학, 수학, 자연과학, 경제학 등에서 미분과 적분이 기본적인 도구로 사용됩니다.  이것의 이해를 하지 않고서는 한치도 앞으로 나갈 수 없습니다.

25장 : 방정식 근 찾기

학창시절 수학 공부하면서 지겹도록 방정식을 풀어 보았을 겁니다.

그런데 아십니까? 우리가 손으로 풀던 문제들은, 딱 손으로 풀 수 있는 정도의 계산량만 요구하는 "연습용" 문제일 뿐이라는 걸요.

실제 현실에서 부닥치는 여러가지 문제들을 방정식으로 모델링하고 이를 풀려고 하면 절대로 손으로 (혹은 대수적으로) 풀 수 없는 경우가 태반입니다.

객관식 문제라면 보기 몇개를 거꾸로 대입시켜 해결할 수 있을 것입니다만... 현실은 주관식이어서  대입해야 할 수는 거의 무한대에 가깝습니다.  이럴 때 필요한 것이 초당 몇백만 번을 계산할 수 있는 컴퓨터의 계산 능력입니다.

24장 : 행렬 (Matrix)

행렬(Matrix)는 행(Row)과 열(Column)로 구성되는 사각형의 격자(Array)에 숫자나 심볼을 배치한 것을 의미합니다.

행렬은 기하학(특히 컴퓨터 그래픽스)이나 통계학에서 시스템을 이루는 다차원의 독립 변수들을 한꺼번에 연산하기 위한 수학적 도구라 볼 수 있습니다.  간단히 말하면 여러 수치를 동일한 방법으로 연산하는 표현이자 도구입니다.

이런 이유로 행렬 또한 컴퓨터로 하는 수치해석의 주요 이슈이며, 매우 중요한 의미를 가집니다.  행렬에 대해서는 고등학교 수학 시간에 필요한 정도는 이미 배웁니다.  만일  기억이 잘 나지 않는다면 행렬에 대한 내용을 복습해 보는 것이 진행하는데 도움이 될 것입니다.

23장 : 다항식 (Polynomial)

이번장 부터는 수치해석(Numerical Analysis)의 기본적인 주제들을 살펴볼 겁니다.

수치해석은 컴퓨터가 가진 뛰어난 연산 능력을 활용하여 복잡한 수학적 문제들을 반복적인 방법으로 풀어내는 것입니다.  현실 세계에서 부닥치는 많은 수학적 문제들은 수치해석이 아니면 풀지 못하는 것들입니다.

그래서 수치해석은 공학, 기초 과학, 통계학 그리고 요즘 뜨고 있는 머신러닝, 빅 데이터 처리 등에 적극 활용되고 있습니다.  다소 수학적인 풀이가 있어 어렵게 느껴지지만, 증명하기 보다는 이해하고 활용하는데 촛점을 맞춘다면 넘지 못할 벽이 아닙니다.

22장 : 방향 그래프 (Directed Graph)

방향 그래프(Directed Graph)는 정점(Vertex)을 연결하는 간선(Edge)에 지금까지와는 달리 방향성을 부여한 것입니다.  그래서 간선을 화살표로 표시합니다.

이것의 의미는 정점 A에서 B로 갈 수는 있어도, B에서 A로는 갈 수 없는 상황을 모델링하는데 유용합니다.  도로를 모델링할 경우 일방통행로가 해당될 것이고, 공정을 모델링할 경우 비가역적(Irreversible) 변이가 이에 해당될 것입니다.

21장 : 가중 그래프 (Weighted Graph)

이번 장에서 배우는 가중 그래프(Weighted Graph)는 정점(Vertex)를 연결하는 간선(Edge)에 가중치를 부여한 것입니다.

예를 들어 정점을 도시라고 생각하고, 간선은 도시를 연결하는 도로라고 한다면, 간선에 매겨진 가중치는 이동하는데 걸리는 비용(시간, 통행료, 연료비 등)이라고 모델링할 수 있습니다.

이런 모델링이 자연스럽기 때문에 가중 그래프의 예로는 두 정점 간의 최소 비용 경로(최단 경로)를 찾는 것이 주요 문제가 됩니다.

자동차의 최단 경로를 안내하는 내비게이션도 도로를 가중 그래프로 모델링하고 그 안에서 최소 비용 경로를 찾는 것입니다.

이번 장에서 가중 그래프를 프로그램으로 표현하는 법, 그리고 최소 비용 신장 트리를 찾기 위한 Kruskal 알고리즘과 최단 경로를 찾기 위한 Dijkstra 알고리즘에 대해 알아볼 것입니다.

20장 : 그래프의 기본 (Graph Basics)

현실 세계에서 모든 사물은 다른 사물과 연관성을 갖습니다.  사람과 사람 사이도 그렇고,  도시와 도시 사이도 그렇습니다.

이런 객체와 그 연관성에 대한 모델링을 그래프(Graph)라고 합니다.  그래프는 객체의 위치는 따지지 않고 오직 연결 관계 즉 위상(Topology)만 따지는 위상수학의 범주에 속합니다.

19장 : 레드-블랙 트리 (Red-Black Tree)

어느덧 검색 알고리즘의 마지막 장입니다.  이번 장에서는 이진트리의 범주를 벗어나지 않으면서 자동으로 균형을 맞추는 알고리즘인 레드-블랙 트리(Red-Black Tree)에 대해 알아봅니다. 

자료를 이진트리로 구성하여 검색 구조로 삼는 이유는 단순한 구조이면서도 자료의 검색, 삽입, 삭제가 효율적이기 때문입니다.  하지만 균형이 맞지 않는 경우 검색 성능이 선형검색과 비슷할 정도로 비효율적입니다.

이 문제를 해결하기 위해 여러가지 알고리즘들이 연구되고 제안되어 왔습니다.  그 중 대표적인 것이 이진트리의 한계에서 벗어나 더 많은 자료를 하나의 노드에 포함하면서 균형 트리를 구현한 B-트리입니다.

18장 : B-트리 (B-Tree) 검색

검색을 위한 자료구조 중에서 잠재력이 가장 큰 것은 이진 트리입니다.  비록 하나의 부모가 두개의 자식밖에 가지질 못하고,  자칫 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어지긴 하지만요. 

그렇지만 이진 트리는 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있어서,  이를 바탕으로 개선하고자 하는 노력이 많이 있어 왔습니다.

그 중에서도 이번 장에서는 두마리의 토끼를 모두 잡은 B-트리에 대해 알아봅니다. 

17장 : 기수 검색 (Radix Search)

컴퓨터의 두뇌인 CPU의 동작을 쪼개어 들어가 보면 결국 0과 1 즉 비트(bit)를 다루는 것을 기본으로 합니다.  컴퓨터에 저장된 모든 데이터는 비트의 배열로 구성됩니다.  하나의 바이트는 8개의 비트로 구성되며,  일반적인 정수형은 4개의 바이트 즉 32비트로 구성됩니다.

지금까지는 데이터를 수학적인 혹인 추상적인 개념으로서 취급했다면, 이 장에서 소개하는 기수 검색(Radix Search)은 데이터를 기본 단위인 비트의 배열로 취급합니다.  비트는 0과 1 두가지 값 밖에 없기 때문에 자연스럽게 자식을 두개 가질 수 있는 이진트리(Binary Tree)와 연결됩니다.

16장 : 해쉬 (Hash)

지금까지 배웠고 또 앞으로 배울 검색 알고리즘들은 모두 자료수 N이 커지면 검색 시간도 더 걸리는 성능을 보여줍니다.  또한 이것이 자연스럽습니다.  이들 알고리즘들은 O(N) 혹은 O(logN)의 성능을 보여 줍니다.

그런데 오늘 배울 검색 알고리즘인 해쉬(Hash)는 자료수 N과 무관하게 일정한 검색 성능을 보여줍니다.  O(1)의 성능입니다.  실로 놀라운 검색 알고리즘입니다.  그런데 알고보면 그 원리는 매우 간단합니다.

입력된 자료가 수치형이든, 스트링이든, 복합 데이터 타입이든 그것을 정수로 변환하는 함수만 정의하면 됩니다.  이 함수를 해쉬 함수라 하며, 입력 자료를 해쉬 함수에 넣어 나온 결과를 해쉬값이라고 합니다.

입력자료에 대해 고른 분포의 해쉬값이 나오는 해쉬함수가 있다면 매우 효율이 높은 해쉬 검색을 구현할 수 있습니다.  하지만 이런 이상적인 경우는 현실에 존재하지 않기 때문에 다른 입력자료가 같은 해쉬값이 나오는 경우가 빈번하게 발생합니다.

15장 : 이진트리 검색 (Binary Tree Search)

가족계획처럼 자식을 둘 이하만 가질 수 있는 이진트리(Binary Tree)는 단촐한 구성 때문에 컴퓨터 알고리즘에서 단골로 등장합니다.  단순화된 이진트리로 알고리즘을 정립한 뒤에 더 복잡한 트리에 적용하는 전략도 많이 쓰입니다.

이번 장에서는 이진트리를 효율적인 검색 구조로 사용하는 방법에 대해서 알아봅니다.  이상적이라면 이진트리의 좌우 균형이 맞아 검색의 효율이 매우 좋습니다.  하지만 이진트리를 구축하는 방법에 따라 균형이 맞지 않을 수 있는데 이때는 검색의 효율이 매우 떨어집니다.