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)는 단촐한 구성 때문에 컴퓨터 알고리즘에서 단골로 등장합니다.  단순화된 이진트리로 알고리즘을 정립한 뒤에 더 복잡한 트리에 적용하는 전략도 많이 쓰입니다.

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