프로그래밍 경시 대회를 준비하기 위한 프로그래밍 연습교재. ACM 국제 대학생 프로그래밍 경시대회와 국제 정보 올림피아드, 탑코더 경시 대회 등의 유명한 국제 프로그래밍 경시대회에 대비하여 알고리즘과 코딩 기법의 이론과 그 연습문제를 다루고 있다.
1장. 시작하면서
로봇 심사위원에 대하여
무기 선택
프로그래밍 관련 힌트
기본 데이터 형식
문제에 대해
2장. 자료 구조
기본 자료 구조
객체 라이브러리
프로그램 설계 예제: 전쟁 게임
카드 표현법
문자열 입출력
전쟁에 이기는 조건
테스트 및 디버깅
3장. 문자열
문자 코드
문자열을 표현하는 방법
프로그램 설계 예제: 회사명 변경
패턴 검색
문자열 조작
회사명 변경 프로그램
문자열 라이브러리 함수
4장. 정렬
정렬 응용 방법
정렬 알고리즘
프로그램 설계 예제: 필드 순위 매기기
정렬 라이브러리 함수
필드 순위 매기기
5장. 계산과 대수
기계 계산
고정도 정수
고정도 계산법
진법
실수
대수
로그
실수 관련 수학 라이브러리
6장. 조합론
기초적인 셈 기법
점화관계
이항계수
다른 셈 수열
재귀호출과 귀납법
7장. 정수론
소수
나눗셈
모듈러 계산
합동
정수론 라이브러리
8장. 백트래킹
백트래킹이란
모든 부분집합 구하기
모든 순열 구하기
프로그램 설계 예제: 여덟 개의 퀸 문제
검색 가지치기
9장 그래프 순회
그래프의 종류
그래프 관련 자료 구조
그래프 순회: 너비 우선 순회
그래프 순회: 깊이 우선 순회
위상 정렬
10장. 그래프 알고리즘
그래프 이론
최소 신장 트리
최단 경로
네트워크 흐름과 이분 매칭
11장. 동적 프로그래밍
탐욕 알고리즘은 그만
편집 거리
경로 재구성
편집 거리 응용
프로그램 설계 예제: 엘리베이터 최적화
12장. 격자
수직 격자
삼각, 육각 격자
프로그램 설계 예: 접시 무게
원 포장법
경도와 위도
13장. 기하
직선
삼각형과 삼각함수
원
프로그램 설계 예제: 총알보다 빠르게
삼각함수 라이브러리
14장. 계산기하
선분과 교차
다각형과 각도 계산
최소 볼록 집합
삼각형으로 쪼개기: 알고리즘 및 관련 문제
격자 관련 알고리즘
기하 라이브러리
부록
ACM 국제 대학생 프로그래밍 경시대회
국제 정보 올림피아드
탑코더 경시 대회
대학원
문제 출제자 명단
참고문헌
해답편
찾아보기