파이썬과 함께하는 자료구조의 이해 (개정판)

파이썬과 함께하는 자료구조의 이해 (개정판)

$33.56
Description
파이썬은 누구나 쉽게 접근할 수 있는 프로그래밍 언어이다. 파이썬은 다른 언어에 비해 간단하여 읽기 쉽고, 수많은 응용 패키지들이 이미 개발되어 있으므로 파이썬 기본 라이브러리 혹은 외부 라이브러리에 포함된 패키지나 모듈을 불러서 사용할 수 있는 언어이다.
일반적으로 컴퓨터 교과과정의 자료구조를 교육할 때는 C-언어, C++ 언어, 혹은 자바 언어로 기본적인 자료구조들을 구현하도록 하여 그 자료구조들의 이해를 돕고 있다. 이러한 언어들은 컴퓨터 분야 전공자들에게 있어 반드시 익혀야 할 언어이지만 오히려 언어 자체가 장벽이 되어 자료구조의 이해를 어렵게 만드는 경우가 종종 발생한다. 하지만 파이썬은 다른 언어들과는 달리 컴퓨터의 기본 지식 없이도 쉽게 프로그래밍을 할 수 있고 이러한 파이썬의 쉬운 접근성은 자료구조에 대한 이해를 더 쉽게 도와준다.
컴퓨터 전공 교과과정에서 자료구조는 아무리 강조해도 지나치지 않을 만큼 중요한 필수과목이다. 여러 프로그래밍 언어를 잘 이해하고 구사할 수 있더라도 자료구조에 대한 기본지식 없이 실제 응용을 위한 효율적인 소프트웨어를 작성하는 데는 한계가 있기 때문이다. 이 책은 필자가 다년간의 강의 경험을 바탕으로 자료구조의 이해에 있어 가장 기본적이고 공통된 부분을 발췌, 정리된 주제와 동시에 비교적 최신 주제인 좌편향(Left-Leaning) 레드 블랙 트리, Tim Sort와 이중 피벗 퀵 정렬(Dual Pivot Quick Sort)을 포함하고 있으며, 대부분의 자료구조에 대해 파이썬으로 구현된 프로그램을 제공한다. 이 책은 연결 리스트, 스택, 큐, 트리 앞부분은 기본적인 개념 위주로 설명하고, 자료구조의 핵심이라 할 수 있는 탐색 트리, 해시 테이블, 정렬, 그래프에 대해 보다 상세히 다루며, 새로운 자료구조를 추가로 소개한다.
저자

양성봉

연세대학교공과대학,학사
UniversityofOklahoma,컴퓨터과학,석사
UniversityofOklahoma,컴퓨터과학,박사
연세대학교컴퓨터과학과교수
현재연세대학교컴퓨터과학과명예교수

목차

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

PART02연결리스트
2.1단순연결리스트
2.2이중연결리스트
2.3원형연결리스트
요약
연습문제

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

PART04트리
4.1트리
4.2이진트리
4.3이진트리의연산
4.4이진힙
요약
연습문제

PART05탐색트리
5.1이진탐색
5.2이진탐색트리
5.2.1탐색연산
5.2.2삽입연산
5.2.3최솟값찾기
5.2.4최솟값삭제연산
5.2.5삭제연산
5.3AVL트리
5.3.1AVL트리의회전연산
5.3.2삽입연산
5.3.3삭제연산
5.42-3트리,레드블랙트리
5.4.12-3트리
5.4.2레드블랙트리
5.5B-트리
5.5.1탐색연산
5.5.2삽입연산
5.5.3삭제연산
5.5.4B-트리의확장
요약
연습문제

PART06해시테이블
6.1해시테이블
6.2해시함수
6.3개방주소방식
6.3.1선형조사
6.3.2이차조사
6.3.3랜덤조사
6.3.4이중해싱
6.4폐쇄주소방식
6.5기타해싱
6.6해시방법의성능비교
요약
연습문제

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

PART08그래프
8.1그래프
8.1.1그래프용어
8.1.2그래프자료구조
8.2그래프탐색
8.2.1깊이우선탐색
8.2.2너비우선탐색
8.3기본적인그래프알고리즘
8.3.1연결성분찾기
8.3.2위상정렬
8.4최소신장트리
8.4.1Kruskal알고리즘
8.4.2Prim알고리즘
8.4.3Sollin알고리즘
8.5최단경로알고리즘
8.5.1Dijkstra알고리즘
8.5.2Floyd-Warshall알고리즘
요약
연습문제

부록
Ⅰ.파이썬메모리
Ⅱ.이중피벗퀵정렬
Ⅲ.TimSort
Ⅳ.정렬의하한
Ⅴ.CutProperty

출판사 서평

이책의특징

독자들의쉬운이해를위해대부분의자료구조를다음의다섯단계에따라설명한다.
1.주어진자료구조에대한이해
2.핵심아이디어소개
3.예제
4.파이썬프로그램
5.수행시간분석

기본적으로각자료구조의필요성을소개하고,자료구조를이해하는데도움이되는핵심아이디어를살펴본다.또한자료구조에대한예제를통해이해를도우며,파이썬(Python3)프로그램으로구현한자료구조를제시하고,수행시간을분석한다.아울러자료구조의응용및활용분야를살펴보고,대부분의파이썬프로그램을PyCharm통합개발환경에서실제로실행시킨결과화면또한보여준다.단,몇몇자료구조들에대한프로그램은너무길어생략하였고개념위주로서술하였다
개정판에는230여개의객관식과주관식연습문제가추가되었고,대부분각Part의내용에대한정확한이해를확인할수있도록출제되었다.적지않은수의문제는IT기업의입사인터뷰문제로도손색없고,또기출문제들도포함되어있다.


이책의내용

Part1자료구조를배우기위한준비에서는자료구조와추상데이터타입,수행시간의분석,수행시간의점근표기법,파이썬언어의기본지식,그리고순환에대해살펴본다.단,본서에서다루는파이썬언어의기본지식은본서에제공된파이썬프로그램을이해하기위해필요한파이썬의일부구문,함수등만을포함하고있다.
Part2리스트에서는단순연결리스트,이중연결리스트,원형연결리스트를설명한다.또한메모리효율적인이중연결리스트를소개한다.
Part3스택과큐에서는스택,큐,데크자료구조를다룬다.
Part4트리에서는일반적인트리,이진트리,이진트리에서의순회및기타기본적인연산,이진힙을각각소개한다.
Part5탐색트리에서는이진탐색트리,AVL트리,2-3트리,레드블랙트리,B-트리를소개하며,특히이진탐색트리,AVL트리는파이썬프로그램을통하여상세히설명한다.
Part6해시테이블에서는해시함수,충돌해결방법으로선형조사,이차조사,랜덤조사,이중해싱,체이닝을배우고,새로운충돌해결방식인2-방향체이닝(Two-WayChaining),뻐꾸기해싱(CuckooHashing)을소개하며,재해싱과동적해싱을각각살펴본다.
Part7정렬에서는기본적인정렬알고리즘인선택정렬,삽입정렬을다루고,이보다효율적인쉘정렬,합병정렬,퀵정렬,힙정렬을살펴보며,특정환경에서사용되는기수정렬과외부정렬을소개한다.또한비교적최근에소개되었고자바의시스템정렬로활용되는이중피벗퀵정렬(DualPivotQuickSort)과파이썬,자바SE7이후버전,안드로이드의시스템정렬로채택된TimSort는부록에서소개한다.
Part8그래프에서는깊이우선탐색,너비우선탐색을공부하고,기본적인그래프알고리즘인연결성분찾기와위상정렬에대해살펴본다.또한Kruskal,Prim,Sollin의최소신장트리알고리즘을소개하고,Dijkstra와Floyd-Warshall최단경로알고리즘을소개한다.
부록에서는파이썬메모리를살펴보며,이중피벗퀵정렬(DualPivotQuickSort)과TimSort를살펴보며,정렬문제의하한을알아보고,최소신장트리알고리즘들이항상정확한해를찾는지를CutProperty의증명을통하여알아본다.