자료검색

책소개

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

C언어, C++언어 혹은 자바 언어들은 컴퓨터 분야 전공자들에게 있어 반드시 익혀야 할 언어이지만 오히려 언어 자체가 장벽이 되어 자료구조의 이해를 어렵게 만드는 경우가 종종 발생한다.

하지만 파이썬은 다른 언어들과는 달리 컴퓨터의 기본 지식 없이도 쉽게 프로그래밍을 할 수 있고 이러한 파이썬의 쉬운 접근성은 자료구조에 대한 이해를 보다 쉽게 만들 수 있다는 타 프로그램 언어와 차별화된 장점을 가지고 있다. 이 책은 파이썬 언어로 자료구조의 기본 개념을 이해하고 궁극적으로 실세계에서 어떤 문제와 마주하더라도 효율적으로 문제를 해결하는 프로그램을 작성할 수 있게 만드는데 그 목적이 있다.

이 책은 필자가 지난 30여 년간의 강의 경험을 바탕으로 자료구조의 이해에 있어 가장 기본적이고 공통된 부분을 발췌, 정리된 주제와 동시에 최신 주제인 좌편향(Left-Leaning) 레드 블랙트리, Tim Sort와 이중피벗퀵정렬(Dual Pivot Quick Sort)을 포함하고 있으며, 대부분의 자료구조에 대해 파이썬으로 구현된 프로그램을 제공한다. 본서는 연결리스트, 스택, 큐, 트리 앞 부분 등은 기본적인 개념 위주로 설명하고, 자료구조의 핵심이라 할 수 있는 탐색트리, 해싱, 정렬, 그래프에 대해 보다 상세히 다루며, 최신 자료구조를 추가로 소개한다.

목차

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

CHAPTER 02 연결리스트
2.1 단순연결리스트
2.2 이중연결리스트
2.3 원형연결리스트
연습문제

CHAPTER 03 스택과 큐
3.1 스택
3.2 스택의 응용
3.3 큐
3.4 데크(Deque)
연습문제

CHAPTER 04 트리
4.1 트리
4.2 이진트리
4.3 이진트리의 연산
4.4 이진힙
연습문제

CHAPTER 05 탐색트리
5.1 이진탐색
5.2 이진탐색트리
5.3 AVL 트리
5.4 2-3 트리, 레드블랙트리
5.5 B-트리
연습문제

CHAPTER 06 해시테이블
6.1 해시테이블
6.2 해시함수
6.3 개방주소방식
6.4 폐쇄주소방식
6.5 기타 해싱
6.6 해시방법의 성능 비교 및 응용
연습문제

CHAPTER 07 정렬
7.1 선택정렬
7.2 삽입정렬
7.3 쉘정렬
7.4 힙정렬
7.5 합병정렬
7.6 퀵정렬
7.7 기수정렬
7.8 외부 정렬
연습문제

CHAPTER 08 그래프
8.1 그래프
8.2 그래프 탐색
8.3 기본적인 그래프 알고리즘
8.4 최소신장트리
8.5 최단경로 알고리즘
연습문제

부록
Ⅰ. 파이썬 메모리
Ⅱ. 이중피벗퀵정렬
Ⅲ. Tim Sort
Ⅳ. 정렬의 하한
Ⅴ. Cut Property