알고리듬으로 생각하기(프로그래밍 언어)

◈ 이 책에서 다루는 내용 ◈

◆ 체스 게임을 하는 최적의 방법과 책을 번역하는 최적의 방법을 찾기 위한 너비 우선 검색 알고리듬
◆ 미로를 빠져나갈 수 있는 생쥐의 수 또는 두 위치 사이의 가장 빠른 경로의 수를 결정하는 다익스트라 알고리듬
◆ 소셜 네트워크의 연결 여부 또는 친구 여부를 결정하기 위한 유니온-파인드 데이터 구조
◆ 매장 판촉에서 제공되는 금액을 결정하기 위한 힙 데이터 구조
◆ 눈송이가 고유한지 여부를 확인하거나 사전에서 복합어를 식별하기 위한 해시 테이블 데이터 구조

◈ 이 책의 대상 독자 ◈

난이도 높은 문제를 해결하는 학습법을 배우려는 모든 프로그래머를 위한 책이다. 이 책을 통해 다양한 데이터 구조와 알고리듬, 문제 풀이에 도움이 되는 유형 및 구현 방법을 배울 수 있다.
이 책의 코드는 전부 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 문제 출처

다니엘 진가로 (Daniel Zingaro)
토론토 대학의 컴퓨터 과학과 조교수이며 토론토 대학의 교육상을 수상했다. 주요 연구 분야는 컴퓨터 과학 교육 연구로써, 컴퓨터 과학 교재를 통한 학습 방법을 연구한다.