자료검색

책소개

컴퓨터를 전공하는 학생들에게 자료구조는 아무리 강조해도 지나치지 않을 만큼 중요한 전공과목이다. 컴퓨터 전공의 근간이 되는 프로그래밍 언어를 잘 이해하고 있더라도 자료구조에 대한 기본지식 없이 실제 응용을 위한 효율적인 소프트웨어를 작성하는 것은 거의 불가능하기 때문이다. 이는 한글을 배우자마자 시나 소설을 쓸 수 없는 것과 같은 이치이다.

이 책은 필자가 지난 30여 년간의 강의 경험을 바탕으로 자료구조의 이해에 있어 가장 기본적이고 공통된 부분을 발췌, 정리함과 동시에 최신 주제인 좌편향(Left-Leaning) 레드블랙트리, Tim Sort와 이중피벗퀵정렬(Dual Pivot Quick Sort), 소셜네트워크분석(Social Network Analysis)의 응용을 추가하였다. 본서는 기존 서적들에서 공통적으로 강조하고 있는 포인터 개념, 연결리스트, 스택, 큐, 트리 앞 부분 등은 기본적인 개념 위주로 설명하고, 자료구조의 핵심이라 할 수 있는 탐색트리, 해싱, 우선순위큐, 정렬, 그래프를 심도 있게 다루며, 아울러 최신 자료구조를 추가로 소개한다.

이 책은 자바 언어에 대한 기본 개념을 갖춘 학부 2학년 학생들을 위하여 집필되었으나, 변리사 및 기술고시의 준비서로서도 충실한 역할을 할 것이며, 올림피아드와 같은 경시대회를 준비하는 학생들에게도 도움이 될 것이다. 또한 전자공학, 수학, 생명공학, 경영학을 전공하는 학생들에게는 자료구조를 스스로 배우고 익힐 수 있는 좋은 입문서가 되리라 생각한다. 독자들이 자료구조의 기본 개념을 이해함으로써 궁극적으로는 실세계에서 어떤 문제와 마주하더라도 효율적으로 문제를 해결하는 프로그램을 작성할 수 있게 되기를 바란다.

목차

CHAPTER 01 자료구조를 배우기 위한 준비
1.1 자료구조와 추상데이터타입
1.2 수행시간의 분석
1.3 수행시간의 점근표기법
1.4 자바 언어에 대한 기본적인 지식
1.5 순환
요약
연습문제

CHAPTER 02 리스트
2.1 배열
2.2 단순연결리스트
2.3 이중연결리스트
2.4 원형연결리스트
요약
연습문제

CHAPTER 03 스택과 큐
3.1 스택
3.2 큐
3.3 데크(Deque)
요약
연습문제

CHAPTER 04 트리
4.1 트리
4.2 이진트리
4.3 이진트리의 연산
4.4 상호배타적 집합을 위한 트리 연산
요약
연습문제

CHAPTER 05 탐색트리
5.1 이진탐색트리
5.1.1 이진탐색트리 클래스
5.1.2 탐색 연산
5.1.3 삽입 연산
5.1.4 최솟값 찾기
5.1.5 최솟값 삭제 연산
5.1.6 삭제 연산
5.2 AVL트리
5.2.1 AVL트리의 회전연산
5.2.2 삽입 연산
5.2.3 삭제 연산
5.3 2-3 트리
5.3.1 탐색 연산
5.3.2 삽입 연산
5.3.3 삭제 연산
5.4 레드블랙트리
5.4.1 레드블랙트리 클래스
5.4.2 탐색 연산
5.4.3 레드블랙트리의 기본 연산
5.4.4 삽입 연산
5.4.5 최솟값 삭제 연산
5.5 B-트리
5.5.1 탐색 연산
5.5.2 삽입 연산
5.5.3 삭제 연산
5.5.4 B-트리의 확장
요약
연습문제

CHAPTER 06 해시테이블
6.1 해시테이블
6.2 해시함수
6.3 자바의 hashCode()
6.4 개방주소방식
6.4.1 선형조사
6.4.2 이차조사
6.4.3 랜덤조사
6.4.4 이중해싱
6.5 폐쇄주소방식
6.6 기타 해싱
6.7 재해시와 동적해싱
6.8 해시방법의 성능 비교 및 응용
요약
연습문제

CHAPTER 07 우선순위큐
7.1 이진힙
7.2 허프만 코딩
7.3 기타 우선순위큐
7.3.1 Leftist 힙
7.3.2 Skew 힙
7.3.3 이항힙
7.3.4 피보나치힙
요약
연습문제

CHAPTER 08 정렬
8.1 선택정렬
8.2 삽입정렬
8.3 쉘정렬
8.4 힙정렬
8.5 합병정렬
8.6 퀵정렬
8.7 정렬의 하한 및 정렬알고리즘의 비교
8.8 기수정렬
8.9 외부정렬
요약
연습문제

CHAPTER 09 그래프
9.1 그래프
9.1.1 그래프 용어
9.1.2 그래프 자료구조
9.2 그래프 탐색
9.2.1 깊이우선탐색
9.2.2 너비우선탐색
9.3 기본적인 그래프 알고리즘
9.3.1 위상정렬
9.3.2 이중연결성분
9.3.3 강연결성분
9.4 최소신장트리
9.4.1 Kruskal 알고리즘
9.4.2 Prim 알고리즘
9.4.3 Sollin 알고리즘
9.5 최단경로 알고리즘
9.5.1 Dijkstra 알고리즘
9.5.2 Bellman-Ford 알고리즘
9.5.3 Floyd-Warshall 알고리즘
9.6 소셜네트워크 분석
요약
연습문제

부록
I 상각분석
II 자바 메모리
III 가비지 컬렉션
IV 이진탐색
V 이진트리 프로그램
VI 이중피벗퀵정렬과 Tim Sort
VII Cut Property