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

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

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

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

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

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

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

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