자료 구조와 알고리즘 파이썬 편 (상식이 통하면 알고리즘도 통한다)

제이웬그로우

저자:제이웬그로우
제이웬그로우는경험많은교육자이자소프트웨어엔지니어로,미국에서상을받은코딩부트캠프인액추얼라이즈(Actualize)의설립자이다.그는복잡한것을쉽게풀어내는데열정적이며,복잡한개념을단순하고쉬운요소로나누어더많은사람들이소프트웨어개발에관심을가지게하는데힘을쏟고있다.

역자:심재철
20년넘게프로그래머로활동하면서데이터베이스및애플리케이션개발등에참여했다.현재는프리랜서로,프로그래밍/데이터베이스/모바일시스템관련컨설팅과번역을하고있다.새로운테크놀로지와다양한프로그래밍언어를실무에활용하고가르치는것을좋아한다.저서로는《핵심만골라배우는코틀린프로그래밍》이있으며,번역서로는《소프트웨어요구사항의정수》,《소프트웨어개발의진주》,《실무에바로적용하는안드로이드프로그래밍》,《스프링인액션》,《카프카핵심가이드》등이있다.

1장자료구조가중요한이유1
1.1자료구조2
1.2배열:기본자료구조3
1.3속도측정5
1.4읽기6
1.5검색9
1.6삽입11
1.7삭제14
1.8집합:단일규칙이효율성에미치는영향15
1.9마무리19
1.10연습문제19

2장알고리즘이중요한이유21
2.1순서가있는배열22
2.2순서가있는배열검색하기25
2.3이진검색27
2.4이진검색vs선형검색31
2.5마무리34
2.6연습문제34

3장빅오표기법35
3.1빅오:데이터요소가N개일때알고리즘은몇단계가필요할까?36
3.2빅오의본질37
3.3세번째유형의알고리즘40
3.4로그42
3.5O(logN)알아보기43
3.6실제예제44
3.7마무리46
3.8연습문제46

4장빅오로코드속도향상하기49
4.1버블정렬49
4.2버블정렬의실제사용51
4.3버블정렬의효율성58
4.4이차문제60
4.5선형솔루션62
4.6마무리65
4.7연습문제65

5장빅오를사용하거나사용하지않는최적화67
5.1선택정렬67
5.2선택정렬의실제사용68
5.3선택정렬의효율성75
5.4상수무시하기76
5.5빅오의범주78
5.6마무리81
5.7연습문제82

6장낙관적인시나리오를위한최적화85
6.1삽입정렬85
6.2삽입정렬의실제사용87
6.3삽입정렬의효율성94
6.4평균적인경우96
6.5실제예제98
6.6마무리101
6.7연습문제101

7장일상적인코드에서의빅오103
7.1짝수의평균104
7.2단어생성기105
7.3배열샘플107
7.4평균섭씨온도108
7.5의류상표109
7.61의개수세기110
7.7회문검사기111
7.8모든곱구하기112
7.9여러데이터세트처리하기114
7.10비밀번호크래커115
7.11마무리118
7.12연습문제118

8장해시테이블을사용한초고속조회123
8.1해시테이블124
8.2해시함수로해싱하기125
8.3재미와이익,특히이익을위한시소러스만들기126
8.4해시테이블조회128
8.5충돌처리하기130
8.6효율적인해시테이블만들기133
8.7데이터구성을위한해시테이블135
8.8속도향상을위한해시테이블137
8.9마무리142
8.10연습문제142

9장스택과큐로간결한코드작성하기145
9.1스택145
9.2추상데이터타입148
9.3스택의실제사용150
9.4코드구현:스택기반코드린터153
9.5제약이있는자료구조의중요성156
9.6큐157
9.7큐의실제사용159
9.8마무리161
9.9연습문제161

10장재귀를사용한재귀적반복163
10.1루프대신재귀163
10.2기저조건165
10.3재귀코드읽기166
10.4컴퓨터의눈으로본재귀169
10.5파일시스템순회172
10.6마무리174
10.7연습문제174

11장재귀적으로작성하는법177
11.1재귀범주:반복실행177
11.2재귀범주:계산182
11.3하향식재귀:새로운사고방식185
11.4계단문제191
11.5애너그램생성195
11.6마무리199
11.7연습문제200

12장동적프로그래밍203
12.1불필요한재귀호출203
12.2빅오를위한작은개선207
12.3재귀의효율성208
12.4중복하위문제209
12.5메모이제이션을통한동적프로그래밍211
12.6상향식접근법을통한동적프로그래밍214
12.7마무리217
12.8연습문제217

13장속도를높이는재귀알고리즘219
13.1분할220
13.2퀵정렬225
13.3퀵정렬의효율성232
13.4퀵정렬의최악의시나리오237
13.5퀵셀렉트238
13.6다른알고리즘의핵심인정렬242
13.7마무리244
13.8연습문제244

14장노드기반자료구조247
14.1연결리스트247
14.2연결리스트구현하기249
14.3읽기251
14.4검색254
14.5삽입255
14.6삭제259
14.7연결리스트연산의효율성262
14.8연결리스트의실제사용262
14.9이중연결리스트263
14.10이중연결리스트기반큐266
14.11마무리268
14.12연습문제268

15장이진탐색트리로속도향상271
15.1트리272
15.2이진탐색트리274
15.3검색275
15.4삽입280
15.5삭제285
15.6이진탐색트리의실제사용296
15.7이진탐색트리순회296
15.8마무리301
15.9연습문제301

16장힙으로우선순위관리하기303
16.1우선순위큐303
16.2힙305
16.3힙속성308
16.4힙삽입309
16.5마지막노드찾기311
16.6힙삭제312
16.7힙vs순서가있는배열316
16.8다시보는마지막노드문제317
16.9배열로힙구현하기319
16.10힙으로구현하는우선순위큐326
16.11마무리326
16.12연습문제327

17장트라이를알아둬서나쁠건없다329
17.1트라이330
17.2단어저장하기332
17.3트라이검색335
17.4트라이검색의효율성339
17.5트라이삽입339
17.6자동완성기능개발하기344
17.7자동완성기능완료하기350
17.8값을포함하는트라이:더개선된자동완성기능350
17.9마무리352
17.10연습문제352

18장그래프하나로전부연결하기355
18.1그래프356
18.2방향그래프358
18.3객체지향그래프구현359
18.4그래프탐색361
18.5깊이우선탐색363
18.6너비우선탐색373
18.7그래프탐색의효율성386
18.8가중그래프389
18.9데이크스트라알고리즘393
18.10마무리410
18.11연습문제411

19장공간제약처리하기415
19.1공간복잡도의빅오415
19.2시간과공간의트레이드오프418
19.3재귀의숨겨진비용421
19.4마무리423
19.5연습문제424

20장코드최적화기법427
20.1전제조건:현재빅오파악하기427
20.2시작하기:상상할수있는최고의빅오428
20.3마법의조회429
20.4패턴인식하기437
20.5탐욕알고리즘445
20.6자료구조변경하기457
20.7마무리464
20.8작별인사464
20.9연습문제465

부록A연습문제해답469
찾아보기505

알고리즘이어려운게아니라설명이문제다
자료구조와알고리즘을설명하는책은주로전문용어나수학적개념이반복되어비전공자나초보자에게는어렵게느껴진다.하지만자료구조와알고리즘은대부분상식선에서이해할수있다.수학적표기방식도그저하나의언어일뿐이며수학으로다루는모든내용도상식적으로설명할수있다.이제상식이통하는,일상언어같은설명으로자료구조와알고리즘을간단하게이해해보자.

이해는말로,학습은손끝으로시작한다
자료구조와알고리즘을배우기어려워하는또다른이유는이론위주의설명때문이다.읽고이해했다고생각했지만막상코딩하려면손이멈췄던경험이누구나있을것이다.개념적이해만으로는충분하지않으며코드를작성하면서배워야진정한학습이된다.귀찮게여기지말고한줄한줄코드를작성해보면서실전감각을키우자.

비전공자를위한입문서지만취준생에게도통한다
입사면접에서는단순히정답을맞추느냐가중요한게아니다.왜이자료구조를썼는지,시간복잡도는어떤지,다른방식보다선택한자료구조가더효율적인이유가무엇인지설명할수있어야한다.비밀번호크래커,소셜네트워크에서친구찾기,최저가항공권찾기,도서관소프트웨어등현실에있을법한실용적인예제들로어떤자료구조를선택해야효율성이극대화되는지,기존의알고리즘을어떻게개선하면성능이향상되는지함께연습할수있다.

이책에서다루는내용
자료구조와알고리즘이중요한이유
빅오표기법으로알고리즘의효율성파악하기
코드효율성을높이는자료구조
우아한코드를위한재귀알고리즘
엄청난성능을자랑하는노드기반자료구조들
메모리효율성을판단하는공간복잡도
몇가지코드최적화기법

대상독자
알고리즘전공서가어려운대학생
취업준비가한창인면접준비자
코딩은되지만알고리즘은부족한실무자