알고리듬으로 생각하기

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 문제 출처