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)입니다.  배열은 동일한 타입의 데이터들이 연속으로 배치된 형태입니다.  동일한 데이터 타입은 간단한 산수로 어드레싱을 할 수 있음을 의미해서 랜덤억세스에 강점이 있는 자료구조입니다.