자료검색

당장 해결하고 싶은 문제와 관련된 알고리즘을 바로 찾아 활용한다

강력한 소프트웨어를 만들려면 효율적인 알고리즘을 사용해야 하지만, 프로그래머들은 문제가 발생하기 전까지는 좀처럼 알고리즘에 관해 생각하지 않는다. 이 책은 다양한 문제를 해결하는 알고리즘을 설명하고 문제에 적합한 알고리즘을 선택하고 구현하는 것을 돕는다. 이론보다 응용에 집중하고, 특정 프로젝트에 쉽게 적용할 수 있는 코드를 여러 프로그램 언어로 제공한다.

당장 해결하고 싶은 문제와 관련된 알고리즘을 바로 찾아 활용한다
강력한 소프트웨어를 만들려면 효율적인 알고리즘을 사용해야 하지만, 프로그래머들은 문제가 발생하기 전까지는 좀처럼 알고리즘에 관해 생각하지 않는다. 이 책은 다양한 문제를 해결하는 알고리즘을 설명하고 문제에 적합한 알고리즘을 선택하고 구현하는 것을 돕는다.
이론보다 응용에 집중했다. 이 책은 특정 프로젝트에 쉽게 적용할 수 있는 코드를 여러 프로그램 언어로 제공한다.

- 특정 코딩 문제를 해결하거나 기존 해결책의 성능을 향상한다.
- 풀고자 하는 문제와 관련된 알고리즘을 빠르게 찾아서 특정 알고리즘이 왜 적합한지 확인한다.
- C, C++, 자바, 루비로 제공된 알고리즘 코드를 설명과 함께 살펴본다.
- 알고리즘이 최고 성능을 발휘할 조건뿐만 아니라 기대 성능을 배운다.
- 비슷한 설계상의 결정이 다른 알고리즘에 미치는 영향을 이해한다.
- 알고리즘의 효율을 높이는 고급 자료구조를 학습한다.

여러분은 이 책에서 응용 소프트웨어에 성공의 열쇠가 되는 알고리즘의 성능을 높이는 방법을 배울 수 있을 것이다.

【추천사】
“저자는 신비로운 학문의 정수를 빼내어 이론과 구현의 완벽한 균형을 갖춘 필수 안내서로 바꾸어 놓는 환상적인 일을 해냈다. 진정으로 알고리즘을 이해하는 일이 훨씬 더 쉬워졌다.”
- 매슈 러셀, Digital Reasoning Systems 사의 CTO이자 『Dojo: The Definitive Guide』 (O'Reilly, 2008)의 저자.

1. 알고리즘은 중요하다

문제를 이해한다 020

필요하다면 실험해본다 022

구원의 알고리즘 025

또 다른 이야기 026

이 이야기의 교훈 028

참고자료 028



2. 알고리즘의 수학

문제 인스턴스의 크기 029

함수의 증가율 032

최고, 평균, 최저 상황에 대한 분석 037

성능 계열 041

연산의 혼합 055

성능측정 연산 056

마지막 한 가지 059

참고자료 059



3. 패턴과 도메인

패턴: 의사전달을 위한 언어 062

알고리즘 패턴의 형식 063

의사코드 패턴 형식 065

설계 형식 066

실험 평가 형식 068

도메인과 알고리즘 069

부동소수점 계산 070

수동 메모리 할당 074

프로그램 언어의 선택 077

참고자료 078



4. 정렬 알고리즘

개요 081

삽입 정렬 088

중앙값 정렬 093

빠른정렬 106

선택 정렬 114

힙 정렬 115

계수 정렬 120

버킷 정렬 123

정렬 알고리즘의 선택 기준 129

참고자료 134



5. 검색

개요 173

깊이-우선 검색 181

너비-우선 검색 188

단일 출발지 최단 거리 192

모든 쌍 최단 경로 205

최소 신장 트리 알고리즘 210

참고자료 213



6. 그래프 알고리즘

개요 173

깊이-우선 검색 181

너비-우선 검색 188

단일 출발지 최단 거리 192

모든 쌍 최단 경로 205

최소 신장 트리 알고리즘 210

참고자료 213



7. 인공지능으로 경로 찾기

개요 215

게임 트리 216

검색 트리 219

깊이-우선 검색 225

너비-우선 검색 235

A* 검색 240

미니맥스 255

네그맥스 261

알파베타 265

참고자료 272



8. 네트워크 흐름 알고리즘

개요 275

최대 흐름 278

이분 맞춤 290

여유 경로에 대한 고찰 293

최소 비용 흐름 298

옮겨싣기 299

수송 300

할당 301

선형 계획법 301

참고자료 303



9. 계산 기하학

개요 305

볼록 껍질 스캔 315

라인스위프 324

최근접 이웃 질의 336

범위 질의 348

참고자료 355



10. 모든 방법이 실패할 때

가정의 변화 357

근사 알고리즘 358

오프라인 알고리즘 358

병렬 알고리즘 359

무작위 알고리즘 359

아주 가끔 틀릴 수도 있는 알고리즘 368

참고자료 372



11. 후기

개요 373

원칙: 자료를 이해한다 373

원칙: 작은 문제로 나눈다 374

원칙: 적합한 자료구조를 선택한다 375

원칙: 성능을 높이려면 저장공간을 추가한다 376

원칙: 확실한 해결책이 없다면, 검색을 구성해본다 377

원칙: 확실한 해결책이 없다면, 해결책이 있는 다른 문제로 환원한다 378

원칙: 알고리즘을 작성하는 건 어렵다-알고리즘을 시험하는 건 더 어렵다 379



부록 성능측정

통계의 기초 381

하드웨어 383

예에 관하여 383