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