14장 : 기본 검색 알고리즘들

알고리즘의 단골 주제 중 가장 큰 꼭지에 해당하는 "검색(Search)"에 대해 시작합니다.  검색은 데이터 집합에서 원하는 데이터를 효율적으로 찾아내는 방법을 연구하는 분야입니다.

책들이 정리되지 않은 상태로 책장에 꽂혀 있다면 원하는 책을 찾기가 매우 어려울 겁니다.  하지만 책의 제목을 기준으로 가나다 순서로 꽂혀 있다면 손쉽게 원하는 책을 찾을 수 있습니다.  이렇게 검색은 데이터 집합을 어떻게 구성해야 효율적으로 데이터를 찾을 수 있는지에 대한 연구가 주를 이룹니다.  그래서 검색은 자료구조(Data Structure)와 밀접한 연관을 가집니다.

13장 : 기수 정렬 (Radix Sort)

정렬 알고리즘에 대한 마지막 장입니다.  마지막 장이니 만큼 다른 관점에서 정렬 문제를 바라보는 기회를 가져보기로 합니다.

컴퓨터 내부에서 숫자는 0과 1의 상태를 가지는 비트(bit)로 표현됩니다.  8비트가 보여 1바이트가 되고,  2바이트는 하나의 워드가 되며,  요즘 정수형은 4바이트로 구성되니 32비트입니다.

최근까지도 32비트 CPU가 널리 쓰였는데  이는 데이터를 32비트 단위로 처리할 수 있어 효율적이었기 때문입니다.

12장 : 쉘 정렬, 병합 정렬 (Shell Sort & Merge Sort)

이 장에서는 두가지의 실용적인 정렬 알고리즘을 소개 드립니다.

하나는 쉘 정렬(Shell Sort)로서 활용도가 높은 삽입 정렬의 성능을 대폭 개선한 것입니다.  삽입 정렬의 장점을 하나도 버리지 않고 장점만 추가된 멋쟁이 알고리즘입니다.  개선의 핵심은 새로 추가된 요소가 들어갈 자리를 순차적으로 비교하지 않고 듬성듬성 건너뛰어 비교하며 찾아낸다는 점입니다.  삽입정렬이 비교횟수에 비해 교환횟수가 지나치게 많았던 단점을 획기적으로 개선한 알고리즘입니다.  단순한 알고리즘이라 구현도 쉽고, 오버헤드도 거의 없습니다.

11장 : 힙 정렬 (Heap Sort)

영어로 힙(Heap)은 "아무렇게나 쌓아놓은 더미"를 의미합니다.  힙 정렬에서 다루는 힙은 아무렇게나 쌓여있는 것 같지만 내부적으로는 수학적인 원리에 의해 데이터를 관리하고 있습니다.  힙은 데이터 집합에서 가장 큰 값을 효율적으로 뽑아낼 수 있는 자료구조입니다.  그래서 힙을 "우선순위 큐"의 예로 많이 듭니다.

힙 정렬은 데이터들을 힙에 쌓아두고 가장 큰 값을 계속 뽑아서 차곡차곡 배치하면 정렬이 된다는 단순한 원리입니다.  원리는 단순하지만 이것을 효율적인 방법으로 구현하는 것은 또 다른 도전이 됩니다.  힙의 모양은 이진트리이기 때문에 통상적인 연결리스트로 힙을 구현할 경우 상당한 오버헤드가 발생하기 때문입니다.

10장 : 퀵 정렬 (Quick Sort)

퀵 정렬은 참 미묘하고도 재밌는 정렬 방법입니다.  일단 퀵 정렬은 일반적인 조건에서 가장 성능이 좋은 정렬 알고리즘 중 하나입니다.  그래서 C나 C++ 언어의 표준 라이브러리에서는 퀵 정렬 혹은 퀵 정렬을 개선한 하이브리드 알고리즘을 사용합니다.  (Java의 경우는 개선된 병합정렬을 사용합니다)

퀵 정렬은 분할을 재귀적으로 수행하는 알고리즘입니다.  그래서 보통의 경우에는 Divide and Conquer 알고리즘이 보여주는 O(NlogN) 성능을 나타내지만 경우에 따라 O(N*N)의 성능이 나오기도 하는 등 변덕스럽기 그지 없습니다.

9장 : 정렬의 기본 (Basic Sorting Algorithms)

정렬(Sorting)은 순서 집합의 원소들을 어떤 기준으로 배열하는 걸 말합니다.  흐트러져 있는 단어카드를 알파벳 순으로 정리하는 걸 연상하면 되겠습니다.  컴퓨터가 취급하는 자료를 정렬된 상태로 저장하면 찾기도 쉽고 관리하기도 쉬워서 이 정렬은 전산학의 전통적인 문제입니다.

역사도 오래되었고 연구도 많이 되었으며,  따라서 그 해법도 매우 다양합니다.  모든 알고리즘이 그렇듯이 모든 상황에서 압도적으로 성능이 좋은 정렬 방법은 없습니다.  그래서 다양한 정렬 알고리즘에 대해서 익혀야 하는 겁니다.  그리고 동일한 문제를 해결하기 위한 다양한 해결 방법을 익히는 것은 문제 해결의 다양하고 창의적인 접근법을 접할 수 있다는 점에서 매우 흥미로운 주제이기도 합니다.

8장 : 재귀 호출 (Recursion)

재귀는 수학적으로 자신의 정의에 자기 자신이 포함되는 경우를 말합니다.  컴퓨터 언어에서 재귀호출은 비슷하게 어떤 함수의 정의가 자기 자신을 호출하는 경우를 의미하며,  수학의 재귀는 컴퓨터 언어의 재귀호출로 표현될 수 있습니다.

흔히 수학의 재귀적 표현은 쉽게 이해하지만 재귀호출과 컴퓨터가 내부적으로 그것을 어떻게 해석하고 실행하는지는 이해하는데 어려움을 겪는 분들이 많습니다.  재귀호출을 이해하기 위해서는 스택과 함수에 대한 근본적인 이해가 있어야 합니다.  이번 장에서는 이런 측면에서 재귀호출을 이해하고 해석하는 방법에 대해서 알아보고자 합니다.

7장 : 트리 (Tree)

트리는 말 그대로 나무의 가지모양을 닮은 자료구조입니다.  나무가지를 뒤집어 놓고 생각해보면 부모 줄기에서 자식 가지가 갈라지고, 그 자식 가지는 또 다른 자식 가지들로 갈라집니다.  이렇게 하나의 부모와 여러개의 자식의 연결을 모델링한 것을 트리(Tree)라고 합니다.

트리는 실제 생활에서도 흔히 볼 수 있는 데이터 구조입니다.  가족관계, 조직도, 행정구역 등이 모두 트리로 모델링될 수 있습니다.

트리는 지금까지 배워온 연결리스트, 배열, 스택, 큐와 달리 비선형 자료구조입니다.  즉 앞과 뒤만으로 설명할 수 없는 고차원의 자료구조입니다.  따라서 비선형 구조만의 독특한 동작과 개념들이 있습니다.  대표적으로 트리의 노드 순서를 매기는 순회(Traversal)를 들 수 있습니다.

6장 : 스택과 큐 (Stack & Queue)

스택과 큐는 단순한 자료구조이지만 이를 응용한 다양한 알고리즘들이 있습니다.  실제 컴퓨팅의 세계에서도 스택과 큐는 매우 중요한 역할을 합니다.  예를 들어 CPU의 명령 코드들은 거의 대부분 스택에 값과 주소들을 저장했다가 빼는 것을 반복합니다.

스택(Stack)은 밑이 막혀있는 프링글스 통처럼 입구와 출구가 하나인 자료구조입니다.   프링글스를 먹는 만큼 계속 채워 넣는다면 제일 아래에 있는 과자는 먹을 일이 없겠지요.  큐(Queue)는 반면에 입구와 출구가 따로 있는 긴 줄입니다.  은행 창구에 서있는 줄을 생각하면 되겠습니다.  누군가 순서를 어기고 새치기를 하면 난리가 나는 그런 줄입니다.

5장 : 연결 리스트 (Linked List)

앞 장에서 기본적인 자료구조(Data Structure)로서 랜덤억세스에 강점이 있는 배열에 대해 살펴 보았습니다.  이번 장에서는 순차적 접근을 염두에 두고 고안된 연결리스트(Linked List)에 대해서 살펴 봅니다.

연결리스트는 정보를 저장하는 노드와 노드간의 연결을 저장하는 링크로 구성됩니다.  노드 하나에 다음 노드로의 링크 하나가 있는 걸 단순 연결리스트라 하고,  노드 하나에 앞 뒤의 연결을 나타내는 두개의 링크가 있으면 이중 연결리스트라고 합니다.

4장 : 배열과 미로 탐색 (Array & Maze)

알고리즘은 본질적으로 데이터를 다루는 방법에 대한 것입니다.  데이터가 구조적으로 조직화되어 다루는 방법까지 포함하게 되면 그것을 자료구조(Data Structure)라고 합니다.   자료구조가 자료를 다루는 방법에 대한 것이라고 본다면 알고리즘의 부분 집합이라 할 수 있습니다.  하지만 그 중요성은 매우 큽니다.

자료구조 중에서 가장 단순한 형태 중 하나는 배열(Array)입니다.  배열은 동일한 타입의 데이터들이 연속으로 배치된 형태입니다.  동일한 데이터 타입은 간단한 산수로 어드레싱을 할 수 있음을 의미해서 랜덤억세스에 강점이 있는 자료구조입니다.

인기글