프로그래밍 스킬은 연습을 통해서만 향상된다
프로그래밍적 상상력을 극대화하는 112가지 유형의 알고리즘과 자료구조

수학 공식을 많이 알고 있다고 해서 문제를 쉽게 풀 수 있는 것은 아닌 것처럼 프로그래밍에서도 알고리즘을 알고 있다고 해서 또는 언어의 문법을 알고 있다고 해서 프로그램을 잘 작성할 수 있는 것은 아니다. 결국 연습을 많이 해 봐야 한다. 이 책은 국제 프로그래밍 경시 대회 유형의 문제를 통해 학생들에게 알고리즘, 프로그래밍을 비롯한 전산학 분야의 다양한 주제에 대한 관심을 고취시켜 준다. 또한 112개의 프로그래밍 문제 외에도 문제를 해결하는 데 필요한 이론 및 핵심 개념도 수록되어 있다. 따라서 이 책을 통해 알고리즘에 대한 이해와 코딩 실력을 효과적으로 향상 시킬 수 있는 가장 효과적인 방법을 습득할 수 있다.

1장. 시작하면서
로봇 심사위원에 대하여
1. Programming-Challenges.com 로봇 심사위원
2. 바야돌리드 대학교 로봇 심사위원
3. 심사위원의 평가 방법
무기 선택
1. 프로그래밍 언어
2. 프로그램을 읽는 방법
3. 표준 입력, 표준 출력
프로그래밍 관련 힌트
기본 데이터 형식
문제에 대해
실마리
참고

2장. 자료 구조
기본 자료 구조
1. 스택
2. 큐
3. 사전
4. 우선 순위 큐
5. 집합
객체 라이브러리
1. C++ 표준 템플릿 라이브러리
2. 자바의 java.util 패키지
프로그램 설계 예제: 전쟁 게임
카드 표현법
문자열 입출력
전쟁에 이기는 조건
테스트 및 디버깅
문제
실마리
참고

3장. 문자열
문자 코드
문자열을 표현하는 방법
프로그램 설계 예제: 회사명 변경
패턴 검색
문자열 조작
회사명 변경 프로그램
문자열 라이브러리 함수
문제
실마리
참고

4장. 정렬
정렬 응용 방법
정렬 알고리즘
프로그램 설계 예제: 필드 순위 매기기
정렬 라이브러리 함수
필드 순위 매기기
문제
실마리
참고

5장. 계산과 대수
기계 계산
1. 정수 라이브러리
고정도 정수
고정도 계산법
진법
실수
1. 실수 처리법
2. 분수
3. 소수점
대수
1. 다항식 처리법
2. 근을 구하는 방법
로그
실수 관련 수학 라이브러리
문제
실마리
참고

6장. 조합론
기초적인 셈 기법
점화관계
이항계수
다른 셈 수열
재귀호출과 귀납법
문제
실마리
참고

7장. 정수론
소수
1. 소수 찾기
2. 소수의 개수
나눗셈
1. 최대공약수
2. 최소공배수
모듈러 계산
합동
1. 합동에 관한 연산
2. 일차합동의 해
3. 디오판토스 방정식
정수론 라이브러리
문제
실마리
참고

8장. 백트래킹
백트래킹이란
모든 부분집합 구하기
모든 순열 구하기
프로그램 설계 예제: 여덟 개의 퀸 문제
검색 가지치기
문제
실마리
참고

9장 그래프 순회
그래프의 종류
그래프 관련 자료 구조
그래프 순회: 너비 우선 순회
1. 너비 우선 검색
2. 순회 점검
3. 경로를 찾는 방법
그래프 순회: 깊이 우선 순회
1. 사이클을 찾는 방법
2. 연결 성분
위상 정렬
문제
실마리

10장. 그래프 알고리즘
그래프 이론
1. 차수 속성
2. 연결성
3. 그래프의 사이클
4. 평면 그래프
최소 신장 트리
최단 경로
1. 다익스트라 알고리즘
2. 전쌍 최단 경로
네트워크 흐름과 이분 매칭
문제
실마리

11장. 동적 프로그래밍
탐욕 알고리즘은 그만
편집 거리
경로 재구성
편집 거리 응용
프로그램 설계 예제: 엘리베이터 최적화
문제
실마리
참고

12장. 격자
수직 격자
1. 순회
2. 쌍대 그래프와 표현법
삼각, 육각 격자
1. 삼각 격자
2. 육각 격자
프로그램 설계 예: 접시 무게
원 포장법
경도와 위도
문제
실마리

13장. 기하
직선
삼각형과 삼각함수
1. 직각삼각형과 피타고라스 정리
2. 삼각함수
3. 삼각형 풀기
원
프로그램 설계 예제: 총알보다 빠르게
삼각함수 라이브러리
문제
실마리

14장. 계산기하
선분과 교차
다각형과 각도 계산
최소 볼록 집합
삼각형으로 쪼개기: 알고리즘 및 관련 문제
1. 반 고흐 알고리즘
2. 넓이 계산
3. 점의 위치
격자 관련 알고리즘
1. 범위 질의
2. 격자 다각형 및 픽의 정리
기하 라이브러리
문제
실마리