◈ 이 책에서 다루는 내용 ◈ ◆ 체스 게임을 하는 최적의 방법과 책을 번역하는 최적의 방법을 찾기 위한 너비 우선 검색 알고리듬 ◆ 미로를 빠져나갈 수 있는 생쥐의 수 또는 두 위치 사이의 가장 빠른 경로의 수를 결정하는 다익스트라 알고리듬 ◆ 소셜 네트워크의 연결 여부 또는 친구 여부를 결정하기 위한 유니온-파인드 데이터 구조 ◆ 매장 판촉에서 제공되는 금액을 결정하기 위한 힙 데이터 구조 ◆ 눈송이가 고유한지 여부를 확인하거나 사전에서 복합어를 식별하기 위한 해시 테이블 데이터 구조 ◈ 이 책의 대상 독자 ◈ 난이도 높은 문제를 해결하는 학습법을 배우려는 모든 프로그래머를 위한 책이다. 이 책을 통해 다양한 데이터 구조와 알고리듬, 문제 풀이에 도움이 되는 유형 및 구현 방법을 배울 수 있다. 이 책의 코드는 전부 C언어로 작성됐으나 C언어의 기초는 다루지는 않는다. 독자가 C/C++에 익숙하다면 바로 시작하는 데 어려움이 없을 것이다. 그 외에 자바나 파이썬 등 다른 언어로 프로그래밍한 경험이 있다면 대부분의 내용은 읽으면서 대략 이해할 수 있을 것이다. 그래도 1장을 시작하기 전에 C언어의 개요를 복습한다면 좀 더 도움이 될 것이다. 특히, 포인터와 동적 메모리 할당에 대해서는 기존의 프로그래밍 경험에 관계없이 숙지해 둘 필요가 있다. 독자에게 추천하는 C언어 책은 K. N. 킹의 『C Programming: A Modern Access, 2nd Edition』(W. W. Norton & Company, 2008)으로, C언어에 익숙한 사람에게도 참고용으로서 유용한 책이다.

1장. 해시 테이블 __문제 1: 고유한 눈송이 ____문제 설명 ____문제 단순화 ____핵심 부분 풀이 ____해법 1: 쌍 비교 ____해법 2: 작업량 줄이기 __해시 테이블 ____해시 테이블 설계 ____해시 테이블 사용 이유 __문제 2: 복합어 ____문제 설명 ____복합어 식별 ____해법 __문제 3: 철자 검사 ____문제 설명 ____해시 테이블 방식의 적합성 판단 ____임시 해법 __요약 __참고 사항 2장. 트리와 재귀 __문제 1: 할로윈 하울 ____문제 설명 ____이진 트리 ____예제 문제 해결 ____이진 트리 표현 ____모든 사탕 모으기 ____완전히 다른 해법 ____최소 경로 이동 ____입력 받기 __재귀 사용 이유 __문제 2: 후손 거리 ____문제 설명 ____입력 받기 ____단일 노드의 후손의 수 ____모든 노드의 후손의 수 ____노드 정렬 ____정보 출력 ____main 함수 __요약 __참고 사항 3장. 메모이제이션과 동적 프로그래밍 __문제 1: 버거 마니아 ____문제 설명 ____계획 세우기 ____최적해의 특성 ____해법 1: 재귀 ____해법 2: 메모이제이션 ____해법 3: 동적 프로그래밍 __메모이제이션과 동적 프로그래밍 ____1단계: 최적해 구조 ____2단계: 재귀 해법 ____3단계: 메모이제이션 ____4단계: 동적 프로그래밍 __문제 2: 구두쇠 ____문제 설명 ____최적해의 특성 ____해법 1: 재귀 ____main 함수 ____해법 2: 메모이제이션 __문제 3: 하키 라이벌 ____문제 설명 ____라이벌 정보 ____최적해의 특성 ____해법 1: 재귀 ____해법 2: 메모이제이션 ____해법 3: 동적 프로그래밍 ____공간 최적화 __문제 4: 통과 방법 ____문제 설명 ____해법: 메모이제이션 __요약 __참고 사항 4장. 그래프 및 너비 우선 탐색 __문제 1: 나이트 추격 ____문제 설명 ____최적 이동 ____최상의 결과 ____변덕스런 해법 ____시간 최적화 __그래프와 BFS ____그래프란? ____그래프와 트리 ____그래프와 BFS __문제 2: 로프 오르기 ____문제 설명 ____해법 1: 동작 찾기 ____해법 2: 리모델링 __문제 3: 책 번역 ____문제 설명 ____그래프 작성 ____BFS 구현 ____총 비용 __요약 __참고 사항 5장. 가중치 그래프의 최단 경로 __문제 1: 생쥐 미로 ____문제 설명 ____BFS 이동 ____가중치 그래프의 최단 경로 ____그래프 작성 ____다익스트라 알고리즘 구현 ____두 가지 최적화 __다익스트라 알고리즘 ____다익스트라 알고리즘의 실행 시간 ____음수-가중치 에지 __문제 2: 할머니 집 찾기 ____문제 설명 ____인접 행렬 ____그래프 작성 ____이상한 경로 ____과제 1: 최단 경로 ____과제 2: 최단 경로 수 __요약 __참고 사항 6장. 이진 탐색 __문제 1: 개미 먹이기 ____문제 설명 ____새로운 형태의 트리 문제 ____입력 받기 ____타당성 시험 ____해법 찾기 __이진 탐색 ____이진 탐색 실행 시간 ____타당성 결정 ____정렬된 배열 탐색 __문제2: 강 건너기 ____문제 설명 ____탐욕 알고리즘 ____타당성 시험 ____해법 찾기 ____입력 받기 __문제 3: 삶의 질 ____문제 설명 ____전체 사각형 정렬 ____이진 탐색 ____타당성 시험 ____좀 더 빠른 타당성 시험 __문제 4: 동굴 문 ____문제 설명 ____하위 작업 풀이 ____선형 탐색 사용 ____이진 탐색 사용 __요약 __참고 사항 7장. 힙과 세그먼트 트리 __문제 1: 수퍼마켓 판촉 행사 ____문제 설명 ____해법 1: 배열의 최댓값과 최솟값 ____최대-힙 ____최소 힙 ____해법 2: 힙 __힙 ____두 가지 응용 사례 ____데이터 구조 선택 __문제 2: 트립 생성 ____문제 설명 ____재귀를 이용한 트립 출력 ____레이블 정렬 ____해법 1: 재귀 ____구간 최대 쿼리 ____세그먼트 트리 ____해법 2: 세그먼트 트리 __세그먼트 트리 __문제 3: 두 합 ____문제 설명 ____세그먼트 트리 채우기 ____세그먼트 트리 쿼리 ____세그먼트 트리 업데이트 ____main 함수 __요약 __참고 사항 8장. 유니온 파인드 __문제 1: 소셜 네트워크 ____문제 설명 ____그래프 모델링 ____해법1: BFS ____유니온 파인드 ____해법 2: 유니온 파인드 ____최적화 1: 크기별 유니온 ____최적화 2: 경로 압축 __유니온 파인드 ____관계: 세 가지 요구사항 ____유니온 파인드 선택 ____최적화 __문제 2: 친구와 적 ____문제 설명 ____확장: 적 ____main 함수 ____파인드와 유니온 ____SetFriends와 SetEnemies ____AreFriends와 AreEnemies __문제 3: 서랍 정리 ____문제 설명 ____동등한 서랍 ____main 함수 ____파인드와 유니온 __요약 __참고 사항 후기 부록 A. 알고리즘 실행 시간 __제한 시간의 한계 __빅오 표기법 ____선형 시간 ____상수 시간 ____추가 예제 ____2차 시간 ____이 책의 빅오 표기법 부록 B. 추가 자료 __고유한 눈송이: 암시적 연결 리스트 __버거 마니아: 해법 재구성 __나이트 추격: 이동 인코딩 __다익스트라 알고리즘: 힙 사용 ____생쥐 미로: 힙을 사용한 추적 ____생쥐 미로: 힙을 사용한 구현 __경로 압축을 압축하기 ____1단계: 삼항 연산자 제거 ____2단계: 할당 연산자 정리 ____3단계: 재귀 이해 부록 C 문제 출처