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

3장 : String 클래스 만들기

2장에서 C++ 언어의 대략적인 문법과 사용법에 대해서 살펴 보았습니다.  하지만 머릿속으로만 익힌 지식은 쉽게 빠져 나갑니다.  3장에서는 이후 진행에 있어 계속 쓰이게 될, 문자열을 저장하는 String 클래스를 만들어 볼 겁니다.   이를 통해서 클래스의 생성자와 제거자, 멤버함수, 연산자 중복 정의 등에 대해서 실습하게 됩니다.

물론 C++ 표준 라이브러리인 STL에서 string 클래스를 제공하고 있으며,  유니코드를 지원하지 않는 점 때문에 실제 현장에서 이 코드가 쓰일 일은 드물 겁니다.  하지만 C++을 배우고 첫번째 만들어 보는 클래스로 String 클래스 만큼 직관적이면서 도전적인 건 없다고 생각합니다.  게다가 임베디드 개발 환경에서는 때로는 이런 간소한 클래스들이 유용할 때가 있습니다.

2장 : C++언어 훑어보기

알고리즘은 문제 해결을 위한 절차이며 이는 개념적인 형태로 존재합니다.  알고리즘이 현실세계에서 위력을 발휘하려면 프로그래밍 언어로 구현되어 컴퓨터에서 동작되어야 합니다.   이 중에서도 객체지향 언어가 알고리즘과 자료구조를 표현하는 데 가장 적합합니다.  그리고 현대적인 프로그래밍 언어가 대부분 추상 데이터 타입으로서의 객체(class)를 지원합니다.

이 강좌에서는 C++ 언어를 매개로 하여 알고리즘을 만나고 구현하고 시험하고 검증하는 여정을 하게 될 겁니다. C++ 언어는 오래된 역사를 가지고 있지만 더 오래된 C라는 언어에서 유래된 것입니다.

1장 : 희망의 나라로, 알고리즘

"C++로 배우는 알고리즘"의 첫번째 챕터로 강의의 목적과 전체적으로 다룰 내용을 간략하게 언급합니다.

"C++로 배우는 알고리즘"은 두가지 큰 주제인 객체지향언어 C++과 알고리즘을 같이 배워보는 과정입니다.  구현 수단으로서의 C++과 구현 대상으로서의 알고리즘을 같이 배우는 것은 적절한 학습 동기와 성취감을 주기에 매우 효과적이라 생각합니다.

하지만 C++에 대한 기본적인 문법은 미리 익혀두는 것이 좋습니다.  이 과정을 통해 머릿속에만 있던 C++ 언어의 사양들이 실제로 어떻게 사용되는지 실감하게 될 것입니다.

C++로 배우는 알고리즘

한동안 잊고 있었는데 오늘 갑자기 생각 났습니다.

2002년 즈음 다니던 회사를 나와 다른 회사로 옮기고 적응하는 잠깐의 기간 동안 "C++로 배우는 알고리즘"이라는 제목으로 온라인 강의를 했습니다.  비트캠퍼스라는 곳에서 했고, 30 챕터로 나누어 대략 40~50시간에 이르는 분량으로 녹화를 했던 것 같습니다.

2002년 한일 월드컵과 맞물려서 정말 힘들었던 여정으로 기억됩니다.

왜 또 알고리즘을 하는가?

벌써 25년 전이네요.  그때 대학생일 때... 우연히 접하게 된 Robert Sedgewick 교수의 "Algorithms in C" 책에 빠져 한동안 헤어나오질 못했습니다.   지금도 헤어져 누더기가 된 이 책이 집에 있을텐데,  구석에 쳐박혀 있어 찾질 못하겠군요.

심지어 군대에 있을때도 이 책을 들고 들어가 짬짬이 보았던 걸로 기억납니다.  왜 그렇게 알고리즘에 천착했을까라고 생각해보니... 그것은 그냥 지적 호기심이었던 같습니다.

프로그래머의 자부심

중학교 2학년때 처음 접했던 Apple II로 인해서 IT 키즈가 된 사람입니다.  이때부터 시작한 IT쪽 특히 소프트웨어 개발 쪽의 인연은 질기고 질기게 끊어지지 않고 현재까지 이어집니다.  벌써 35년이 되어 가는군요.

그동안 밥벌이하느라 바쁘게만 살아와 30년을 넘게 이 분야에서 뭘했나 흔적조차 남기기 어려웠습니다.  그냥 저냥 이대로 살다가 은퇴하겠지요.

그런데 이제 은퇴도 못하게 생겼습니다.  IT쪽의 인력 수요는 여전히 많은데, 대체 젊고 총기 발랄한 IT키즈들은 보이질 않습니다.   모두들 사시, 행시, 공시, 의시에 달려들고 있습니다. 그나마 IT쪽에서는 게임 회사들이 블랙홀 처럼 남은 인재들을 싹 쓸어갑니다.  그러니 은퇴하고 싶어도 은퇴하질 못합니다.