보통 자료구조나 알고리즘 관련 책은 생각만 해도 어려울 것 같고, 잠이 올 것 같다. 그래서 해야된다는 굳은 의지가 아니면, 보통 앞에서 3~4장을 보고 덮어두는 경우가 허다할 것이다.
그렇다면, 이 책으로 다시 한번 시작해보자. 글과 그림으로 재미있게 알고리즘을 이해할 수 있다. 처음부터 끝까지 전혀 지루하지 않게 읽을 수 있었다.
개인적으로 자료구조, 알고리즘 책은 2~3권 교차해서 읽으면 좋은데, 본인도 4권을 가지고 있다. 그 중 제일 재미없고 어려운 책은 대학 교재였다. 처음부터 이 책으로 시작했으면, 대학 교재가 이 책이었으면, 재미와 지식을 둘 다 가졌을텐데 하는 아쉬움이 들었다. 오히려 전공자에게는 알고리즘을 포기하게 만드는 단점이랄까~
모두 읽고 나니 비전공자도 쉽게 읽을 수 있는 난이도라고 생각한다. 다만 예제가 C언어인데, 개념을 익히는데, 전혀 문제가 되지 않는다. 오히려, 예제에서 연산을 하나하나 구현하므로, 다른 언어와 비교하면서 살펴보기를 추천한다.
책의 구성은 크게 3개의 파트로 되어 있는데, Part 01에서는 자료 구조(리스트, 스택, 큐, 트리)를 살펴보고, Part 02는 알고리즘(정렬, 탐색, 우선순위 큐와 힙, 해시테이블, 그래프)을 설명한다. 마지막 Part 03은 알고리즘 설계 기법(성능 분석, 분할 정복, 동적 계획법, 탐욕 알고리즘, 백트래킹)에 관해 설명한다.
각 장을 설명하면 아래와 같다.
먼저, Chapter 00은 자료구조 개념과 알고리즘의 정의에 관해 알아보고, 앞으로 다룰 예제에서 꼭 필요한 C언어의 포인터, 구조체, 메모리 레이아웃(스택, 힙)으로 몸풀기를 진행한다.
본격적으로 Chapter 01에서는 리스트의 개념을 이해하고, 배열과 차이점, 링크드 리스트, 더블 링크드 리스트, 환형 링크드 리스트를 구현한다.
Chapter 02는 우리에게도 아주 익숙한 스택이다. 스택의 개념과 연산을 이해하고, 배열 기반 스택과 링크드 리스트 기반 스택을 구현한다.
Chapter 03은 큐의 개념과 주요 연산을 이해하고, 순환 큐와 링크드 큐를 구현한다.
Chapter 04는 트리다. 트리의 개념을 이해하고, 이진 트리와 수식 트리, 분리 집합을 살펴본다.
Chapter 05에서는 정렬의 개념을 이해하고, 버블 정렬, 삽입 정렬, 퀵 정렬을 구현한다.
Chapter 06은 탐색의 개념에 관해 알아보고 순차 탐색, 이진 탐색의 개념을 이해한다. 그리고 이진 탐색 트리와 레드 블랙 트리를 구현한다.
Chapter 07은 우선순위 큐와 힙(메모리 힙과는 다르며, 완전 이진 트리의 종류)의 개념을 이해하고, 힙 기반 우선순위 큐를 구현한다.
Chapter 08에서는 해시 테이블의 개념을 이해하고, 해시 테이블과 해시 함수를 구현한다. 또한 해시 테이블의 주소 충돌 해결 방법도 다룬다.
Chapter 09는 그래프의 개념과 표현 방법을 이해하고, 그래프의 순회 기법과 위상 정렬, 최소 신장트리 기법과 최단 경로 탐색 알고리즘을 살펴본다.
Chapter 10은 문자열 탐색 알고리즘의 개념을 알아보고, 카프-라빈 알고리즘, KMP 알고리즘, 보이어-무어 알고리즘을 구현한다.
Chapter 11에서는 알고리즘 성능 측정 기준(정확성, 작업량, 메모리 사용량, 단순성, 최적성)을 이해하고, 수행 시간의 개념과 표기법을 알아본다 .
Chapter 12는 알고리즘 설계 기법의 하나인 분할 정복을 알아본다.
Chapter 13은 동적 계획법의 개념을 살펴보고, 동적 계획법을 이용하여 피보나치 수 구하기, LCS(최장 공통 부분 수열) 알고리즘을 설계한다.
Chapter 14는 탐욕 알고리즘의 개념을 이해하고, 탐욕적 관점에서 그래프에서 배운 크루스칼과 데이크스트라(다익스트라) 알고리즘을 살펴본다. 허프만 코딩(데이터 압축)도 구현한다.
마지막, Chapter 15에서는 백트래킹 개념을 이해하고, 미로 탈출 알고리즘과 N개의 퀸 문제 풀이 알고리즘을 설계한다.
각 장의 시작은 학습 목표인데, 이 장에서 설명하는 핵심 개념과 학습 흐름을 정리한다. 핵심 개념은 알고리즘의 탄생 배경이라든지, 적절한 예시(나폴레옹의 전술, 그리스-로마 신화, 수학자 레온하르트 오일러의 이야기)를 들어 전혀 지루하지 않고, 흥미를 부추기며 알고리즘 속으로 독자를 끌어 들인다. 알고리즘을 설명할 때는 그림을 이용하여 단계별로 설명하므로 쉽고, 페이지도 금방금방 넘어간다. ㅎㅎ, 이어서 응용 알고리즘 설명과 C언어 구현 예제 및 실행 결과, 마지막 연습 문제로 마무리한다.
<깊이 우선 탐색 개념 설명>
중간 중간 "!여기서 잠깐", "NOTE"는 관련 용어이나 참고 사항, 보충 설명이 있을 때마다 나오니, 읽어 보고 참고하시면 된다.
이 책에서 좋았던 부분은 단연코 알고리즘과 관련하여 흥미를 끌만한 다양한 내용이며, 저자의 위트 넘치는 표현이다. 그리고 빼놓을 수 없는 부분이 예제의 완성도이다. 변수의 선언이라든지, 소스 코드 분리, 테스트 코드, 바로 현업에 사용해도 전혀 어색하지 않는다고 개인적으로 생각한다.
636페이지의 분량이지만, 읽다 보면 생각보다 빨리 읽을 수 있을 것이다. 개념을 설명하기 위한 그림과 예제가 많아서 이해하기도 쉽고, 읽기도 쉬웠다. 책 내용과 그림은 퍼플계열인데, 그 부분도 좋았다.
개인적으로는 10장의 문자열 탐색 알고리즘이 많이 어려웠다. 리뷰 다 쓰고 다시 읽어 봐야 겠다. 다른 장들은 비교적 어렵지 않게 읽혔다. 단점으로는 연습문제 답도 만들어 주세요~, 이러다 아무도 안 읽고 버려질 수 있어요. 제발~
마지막으로 우리가 알고리즘 책을 봐야하는 이유에 관한 저자의 인용 문구로 마무리하고자 합니다.
알고리즘을 체계적으로 공부하지 않아도 프로그래밍을 할 수 있지만, 더 나은 프로그래머가 되기 위해서는 알고리즘에 대해 제대로 알아둘 필요가 있습니다.
Chapter 00 알아두면 쓸 데 있는 자료구조와 알고리즘, p7
"한빛미디어<나는 리뷰어다> 활동을 위해서 책을 제공받아 작성된 서평입니다."
#자료구조 #알고리즘 #이것이자료구조알고리즘이다withC언어 #이것이자료구조알고리즘이다 #한빛미디어 #박상현 # 다익스트라 #데이크스트라 #허프만코딩
예제소스
