진짜 쉬운 자료 구조와 알고리즘 파이썬 편

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.5 O(log N) 알아보기 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.6 1의 개수 세기 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