데이터구조 원리와 응용

이 책은 기존 교재들의 이러한 한계를 극복하기 위한 대안으로 준비되었다. 저자는 무엇 보다 최근의 추세에 맞추어 국내외의 최신 이론과 개념들을 포함하고자 노력했으며 누구나 이해하기 쉬운 방식으로 학습 내용을 전달하기위해 텍스트에 주로 의존한 전달 대신 다이어그램, 그림 등을 충분히 활용해서 학습 내용을 알기 쉽게 전달하는 것에 초점을 두어 집필하였다. 여기에 더하여 또 하나의 특징은 주관식 퀴즈 형태의 심층문제들을 다수 수록해서 스스로 공부하는 독자에게는 학습성과 점검의 도구를, 토론식 수업을 지향하는 교강사들에게는 수업에 직접 활용 가능한 퀴즈 문제의 풀을 제공한다는 점이다. 가장 중요한 특징으로, 응용을 중심으로 한 학습을 인도한다는 점이다. 저자는 책을 만들면서 이론 학습 위주가 아닌 알고리즘 작성과 프로그래밍 과제를 수행하도록 적극 유도하는 매우 실전적인 응용문제나 심층문제를 다수 수록하려 노력했다.

PART I 기본도구 CHAPTER 1 알고리즘 분석 1.1 실행시간 1.1.1 평균실행시간과 최악실행시간 1.1.2 실행시간 구하기 1.2 의사코드 1.2.1의사코드 문법 1.3 실행시간 측정과 표기 1.3.1 임의접근기계 모델 1.3.2 원시작업 1.3.3 실행시간 측정 1.3.4 실행시간 표기 1.3.5 점근분석 29 1.3.6 분석의 지름길 1.3.7 Big-Oh의 친척들 1.4 전형적인 함수들의 증가율 1.5 알아야 할 수학적 배경 1.6 응용문제 1.6.1 행렬에서 특정원소 찾기 1.6.2 비트행렬에서 최대 1행 찾기 1.6.3 누적평균 요약 연습문제 심층문제 CHAPTER 2 재귀 2.1 재귀알고리즘 2.2 재귀의 작동 원리 2.3 재귀의 기본 규칙 2.3.1 잘못 설계된 재귀 2.3.2 잘 설계된 재귀 2.4 응용문제 2.4.1 재귀적 곱하기와 나누기 2.4.2 하노이탑 요약 연습문제 심층문제 CHAPTER 3 기초 데이터구조 3.1 데이터구조의 기본 재료 3.2 배열 3.2.1 1차원 배열 3.2.2 다차원 배열 3.3 연결리스트 3.3.1 단일연결리스트 3.3.2 이중연결리스트 3.3.3 원형연결리스트 3.3.4 헤더와 트레일러 3.3.5 그외의 연결리스트 요약 연습문제 심층문제 PART II 추상자료형 CHAPTER 4 리스트 4.1 추상자료형 4.2 리스트 ADT 4.2.1 리스트 ADT 메쏘드 4.3 리스트 ADT 구현 4.3.1 배열을 이용한 리스트 구현 4.3.2 연결리스트를 이용한 리스트 구현 4.3.3 리스트 구현의 성능 4.4 리스트 ADT 확장 4.4.1 그룹 4.4.2 공유 4.5 응용문제 4.5.1 원형배열 4.5.2 다항식 4.5.3 생일 케이크 요약 연습문제 심층문제 CHAPTER 5 집합 5.1 집합 ADT 5.2 집합 ADT 메쏘드 5.3 집합 ADT 구현 5.3.1 연결리스트에 저장된 집합 5.3.2 연결리스트에 저장된 집합에 대한 메쏘드 구현 5.4 응용문제 5.4.1 비파괴적인 합집합, 교집합 메쏘드 5.4.2 정수 범위로 매핑 가능한 집합 요약 연습문제 심층문제 CHAPTER 6 스택 6.1 스택 ADT 6.2 스택 ADT 메쏘드 6.3 스택 응용 6.4 스택 ADT 구현 6.4.1 배열에 기초한 스택 6.4.2 연결리스트에 기초한 스택 6.5 응용문제 6.5.1 심볼 균형 6.5.2 기간 6.5.3 후위수식 6.5.4 다중스택 요약 연습문제 심층문제 CHAPTER 7 큐 7.1 큐 ADT 7.2 큐 ADT 메쏘드 7.3 큐 ADT 구현 7.3.1 배열에 기초한 큐 7.3.2 연결리스트에 기초한 큐 7.4 데크 ADT 7.4.1 데크 ADT 메쏘드 7.4.2 데크 ADT 구현 7.5 응용문제 7.5.1 두 개의 스택으로 큐 만들기 7.5.2 두 개의 큐로 스택 만들기 요약 연습문제 심층문제 CHAPTER 8 트리 8.1 트리 ADT 8.2 트리 용어 8.3 트리 ADT 메쏘드 8.3.1 깊이와 높이 8.3.2 트리 순회 8.4 이진트리 ADT 8.5 이진트리 ADT 메쏘드 8.5.1 깊이와 높이 8.5.2 이진트리 순회 8.5.3 이진트리에 대한 오일러 투어 순회 8.6 이진트리 ADT 구현과 메쏘드 8.6.1 배열에 기초한 이진트리 8.6.2 연결리스트에 기초한 이진트리 8.7 트리 ADT 구현과 메쏘드 8.8 응용 문제 8.8.1 계승자 8.8.2 로만노드 8.8.3 양자택일식 문답시스템 요약 연습문제 심층문제 CHAPTER 9 분리집합 9.1 분리집합 ADT 9.2 분리집합 ADT 메쏘드 9.3 분리집합 ADT 구현 9.3.1 리스트에 기초한 분리집합 구현 9.3.2 트리에 기초한 분리집합 구현 9.4 응용문제 9.4.1 높이에 의한 합집합 9.4.2 부분적 경로압축 요약 연습문제 심층문제 APPENDIX : 연습문제의 답