C 언어로 배우는 알고리즘 입문

정선된 예제와 절제된 설명으로 알고리즘의 정석을 보여준다

각 분야별로 정선된 알고리즘 예제를 통해 알고리즘을 쉽고 효율적으로 학습할 수 있게 해준다. 제시한 기본 알고리즘을 완전히 이해하면 좀더 현실적인 문제도 풀 수 있을 것이다.

특히, 각 장에서 제시한 모든 예제와 연습문제에 대한 해답은 비주얼 C++와 gcc에서 테스트한 완전한 소스다.

• 수학 관련 알고리즘 : 수치 적분법, 테일러 전개, 비선형 방정식, 연립방정식의 해법, 보간과 최소제곱법, 긴 자리수 계산, 선형 계획법
• 정렬과 탐색 알고리즘: 직접 선택법, 거품 정렬, 기본 삽입법, 셸 정렬, 축차 탐색과 이분 탐색, 해시, 병합, 문자열 치환, 문자열 조합
• 기본 데이터 구조와 응용: 스택, 큐, 리스트, 역폴란드 기법과 파싱, 자기 재편성 탐색과 해시의 체인법
• 기본 트리와 그 응용 : 이진 탐색 트리, 힙, 다항식 트리, 결정 트리, 힙 정렬과 지능형 데이터베이스
• 다양한 퍼즐 게임 알고리즘과 백 트래킹, 동적 프로그래밍
• 프로그래밍 세계의 정리나 공식이라 할 수 있는 알고리즘의 개요
• 알고리즘 구현을 위한 핵심 개념, 재귀
• 네비게이터의 핵심 이론, 그래프

추천평(미디어서평)

알고리즘하면 큰 맘 먹고 머리 싸매면서 공부해야 하는 주제로 유명하다. 최근에 보았던 『누워서 읽는 알고리즘』이 지친 프로그래머의 머리를 식혀주고 생각하는 방법을 알려주었다면, 이 책은 고등학교때 배웠던 『수학의 정석』처럼 어떤 시험이든지, 어떤 문제든지 풀 수 있게 만들 것 같은 알고리즘의 정석 같은 책이다. - 방성민(『안전한 프로그램을 만드는 Secure Coding 핵심 원리』 저자)

장별 내용 요약

01장. 워밍업
2장 이후부터 다루는 분야들과는 다소 거리가 있는, 비교적 간단한 알고리즘을 통해 기초를 다진다.

02장. 수치 계산
역사가 아주 오래되어 이론적으로 상당히 체계화된 수치 적분법, 테일러 전개, 비선형 방정식과 연립 방정식의 해법, 보간, 최소 제곱법 등과 같은 수치 계산 알고리즘에 대해 알아본다.

03장. 정렬과 탐색
데이터를 처리하는 기본 방법인 정렬 탐색에 대해 알아본다. 직접 선택법, 거품 정렬, 기본 삽입법, 셸 정렬 등의 정렬법과 축차 탐색과 이분 탐색, 해시 등의 탐색법 뿐만 아니라 병합, 문자열 치환, 문자열 조합 등에 대해서도 설명한다.

04장. 재귀
트리, 그래프와 같은 데이터 구조를 다루는 알고리즘을 위해 꼭 알아야 하는 재귀에 대해 알아본다. 팩토리얼, 피보나치 수열 등의 간단한 예로 시작해 하노이의 탑이나 미로와 같은 문제와 퀵 정렬 등을 재귀를 이용해 구현해본다.

05장. 데이터 구조
대량의 데이터를 다룰 때는 어떤 데이터 구조를 이용하느냐에 따라 사용하는 알고리즘이 달라질 정도로 데이터 구조와 알고리즘은 서로 밀접한 관련이 있다. 이 장에서는 스택, 큐, 리스트 등의 데이터 구조에 대해 알아보고, 스택을 응용한 역폴란드 기법과 파싱, 리스트를 응용한 자기 재편성 탐색과 체인법에 대해 알아본다.

06장. 트리
조건에 따라 구분되는 데이터를 가계도나 회사 조직도와 같이 계층적으로 나타내기에 적합한 트리에 대해 알아본다. 이진 트리를 중심으로 트리를 생성하고 순회하는 방법을 설명하고, 트리를 응용한 예로 힙 정렬과 지능형 데이터베이스에 대해 소개한다

07장. 그래프
트리의 각 노드가 여러 방향으로 서로 연결되어 있는 그래프에 대해 알아본다. 이 장에서 설명하는 그래프에서 지점간 최단 거리를 찾는 방법으로 가장 빨리 갈 수 있는 도로 찾기와 같은 문제를 풀 수 있다.

08장. 그래픽
2차원 도형을 방정식으로 나타내 좌표변환으로 평행이동, 회전, 확대, 축소 등을 하고, 3차원 공간의 좌표를 2차원 평면에 투영하는 방법과 관련 라이브러리에 대해 알아본다.

09장. 퍼즐 게임
알고리즘을 이용해 마방진과 전략이 있는 가위바위보와 같은 퍼즐 게임 등을 해결하는 방법을 알아본다. 그리고 특정 알고리즘을 적용하지 못하고 모든 상황을 일일이 조사해야 할 때 이를 쉽게 해결할 수 있는 백 트래킹과 동적 프로그래밍에 대해서도 알아본다.