자료구조의 이해(자바와 함께하는)

이 책의 주요 내용

본서의 각 Part의 내용을 간략히 나열해보면 다음과 같다.
ㆍPart 1 자료구조를 배우기 위한 준비
자료구조와 추상 데이터 타입, 수행 시간의 분석, 수행 시간의 점근 표기법, 자바 언어의 기본 지식, 그리고 순환에 대해 살펴본다.
ㆍPart 2 리스트
배열, 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트를 설명한다.
ㆍPart 3 스택과 큐
스택, 큐, 데크 자료구조를 다룬다.
ㆍPart 4 트리
일반적인 트리, 이진 트리, 이진 트리에서의 순회 및 기타 기본적인 연산, 집합을 위한 트리 연산으로서 Union-Find 연산을 각각 소개한다.
ㆍPart 5 탐색 트리
이진 탐색 트리, AVL 트리, 2-3 트리, 레드 블랙 트리(Left-Leaning Red Black Tree), B-트리를 소개하며, 특히 이진 탐색 트리, AVL 트리, 레드 블랙 트리는 자바 프로그램을 통하여 상세히 설명한다.
ㆍPart 6 해시 테이블
해시 함수, 충돌 해결 방법으로 선형 조사, 이차 조사, 랜덤 조사, 이중 해싱, 체이닝을 배우고, 새로운 충돌 해결 방식인 융합 해싱(Coalesced Hashing), 2-방향 체이닝(Two-Way Chaining), 뻐꾸기 해싱(Cuckoo Hashing) 을 소개하며, 재해싱과 동적 해싱을 각각 살펴본다.
ㆍPart 7 우선순위 큐
이진 힙과 그의 응용인 허프만 압축 알고리즘을 소개하고, Leftist 힙, Skew 힙, 이항 힙(Binomial Heap), 피보나치 힙(Fibonacci Heap)을 각각 소개한다.
ㆍPart 8 정렬
기본적인 정렬 알고리즘인 선택 정렬, 삽입 정렬을 다루고, 이보다 효율적인 쉘 정렬, 합병 정렬, 퀵 정렬, 힙 정렬을 살펴보며, 정렬 문제의 하한을 알아보고, 특정 환경에서 사용되는 기수 정렬과 외부 정렬을 소개한다. 또한 비교적 최근에 소개되었고 자바, 파이선, 안드로이드의 시스템 정렬로 채택된 Tim Sort와 자바의 원시 타입 시스템 정렬인 이중 피벗 퀵 정렬(Dual Pivot Quicksort)은 부록에서 소개한다.
ㆍPart 9 그래프
깊이 우선 탐색, 너비 우선 탐색을 공부하고, 기본적인 그래프 알고리즘인 위상 정렬, 이중 연결 성분, 강 연결 성분 알고리즘을 살펴본다. 또한 Kruskal, Prim, Sollin의 최소 신장 트리 알고리즘을 소개하고, Dijkstra, Bellman-Ford, Floyd-Warshall 최단 경로 알고리즘을 이해하고 분석하며 마지막으로 그래프의 응용으로서 소셜 네트워크 분석(Social Network Analysis)의 중심성(Centrality)과 커뮤니티 찾기(Community Detection)를 소개한다.
ㆍ부록
상각 분석(Amortized Analysis)을 상세히 알아보고, 자바 메모리를 살펴보며, 자바의 가비지 컬렉션(Garbage Collection)의 여러 가지 방법을 소개한다. 또한 이진 탐색 트리와 관련된 이진 탐색을 소개하며, Part 4의 이진 트리를 위한 자바 프로그램을 제공하며, Tim Sort와 이중 피벗 퀵 정렬(Dual Pivot Quick Sort)을 살펴보며, 최소 신장 트리 알고리즘들이 왜 항상 정확한 해를 반환하는 지를 Cut Property의 증명을 통하여 알아본다.

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

특히 개정판에는 270여 개의 객관식과 주관식 연습문제가 추가되었고, 대부분 각 Part의 내용에 대한 정확한 이해를 확인할 수 있도록 출제되었다. 적지 않은 수의 문제는 IT 기업의 입사 인터뷰 문제로도 손색없고, 또 기출 문제들도 포함되어 있다. 그리고 각 Part 맨뒤에는 IT회사의 Job 인터뷰 문제가 쉬어가기로 추가되었다.
일일이 다 열거할 수는 없지만, 마지막 단계에서 원고를 꼼꼼히 읽고 검토해준 양원석군의 도움에 고마움을 표한다. 또한 풍부한 저작 활동 경험으로 지속적인 조언을 아끼지 않으신 최윤철 교수님의 성원에 깊은 감사를 드린다. 아울러 이 책의 시작과 완성의 전 과정을 이끌어 주신 생능출판사 김승기 사장님과 최복락 상무님, 출판 과정에서 많이 애써 주신 김민보 차장님 및 편집 담당 관계자분들께도 진심으로 감사드린다.

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

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

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

PART 04 트리
4.1 트리
4.2 이진 트리
4.3 이진 트리의 연산
4.4 서로소 집합을 위한 트리 연산
■요약
■연습문제

PART 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-트리의 확장
■요약
■연습문제

PART 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 해시 방법의 성능 비교
■요약
■연습문제

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

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

PART 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

참고문헌
찾아보기

양성봉 연세대학교 공과대학, 학사
University of Oklahoma, 컴퓨터과학, 석사
University of Oklahoma, 컴퓨터과학, 박사
연세대학교 컴퓨터과학과 교수
현재 연세대학교 컴퓨터과학과 명예교수