자료검색

책소개

이 책은 프로그래밍적 사고와 알고리즘의 학습과 훈련을 위한 교재이다. 특정 프로그래밍 언어에 대한 능숙한 사용과 달리 프로그래밍을 잘 하기 위해서는 수학적이고 논리적인 사고과정을 필요로 한다. 컴퓨터 알고리즘에 관한 100여가지 선별된 프로그래밍 경시대회 문제로 문제 해결능력과 두뇌훈련에 도움이 되도록 구성되었다. 프로그래밍 대회를 준비하는 학생들의 실습문제로는 물론 알고리즘이나 자료구조의 학습을 위해 다양하게 사고하고 다양한 상황에 대처하는 문제 풀이용으로도 사용할 수 있다.

프로그래밍 경시대회 중 가장 큰 대회라고 할 수 있는 ACM 국제 대학생 프로그래밍 경시대회, 국제 정보 올림피아드, 탑코더 경시대회를 준비하할 수 있도록 하였다. 경시대회에서 우수한 성적을 거두기 위해 알고리즘에 대한 이해는 물론 코딩실력도 뒷받침 해 주어야 한다. 그러기 위해서 이 책의 각 장에서는 다양한 유형의 문제를 해결하기 위해 필요한 자료 구조와 알고리즘에 대해 설명하고, 그 내용을 사용하여 풀어낼 수 있는 문제들을 소개하고 있다. C언어로 여러 핵심적인 알고리즘을 구현해놓았기 때문에 알고리즘을 이해하고 실제로 구현하는 데도 어려움 없이 이해할 수 있을 것이다. (C언어 외에 파스칼이나 C++, 자바 등을 사용하는 사람들도 이해할 수 있을 만한 방식으로 구현되어 있다.)

목차

1장. 시작하면서
로봇 심사위원에 대하여
1. Programming-Challenges.com 로봇 심사위원
2. 바야돌리드 대학교 로봇 심사위원
3. 심사위원의 평가 방법
무기 선택
1. 프로그래밍 언어
2. 프로그램을 읽는 방법
3. 표준 입력, 표준 출력
프로그래밍 관련 힌트
기본 데이터 형식
문제에 대해
문제 1. 3n+1 문제(The 3n+1 Problem)
문제 2. 지뢰 찾기(Minesweeper)
문제 3. 여행(The Trip)
문제 4. LCD 디스플레이(LCD Display)
문제 5. 그래픽 편집기(Graphical Editor)
문제 6. 인터프리터(Interpreter)
문제 7. 체크 확인(Check the Check)
문제 8. 호주식 투표법(Australian Voting)
실마리
참고

2장. 자료 구조
기본 자료 구조
1. 스택
2. 큐
3. 사전
4. 우선 순위 큐
5. 집합
객체 라이브러리
1. C++ 표준 템플릿 라이브러리
2. 자바의 java.util 패키지
프로그램 설계 예제: 전쟁 게임
카드 표현법
문자열 입출력
전쟁에 이기는 조건
테스트 및 디버깅
문제 9. 유쾌한 점퍼(Jolly Jumpers)
문제 10. 포커 패(Poker Hands)
문제 11. 동맹 휴업(Hartal)
문제 12. 암호 깨기(Crypt Kicker)
문제 13. 쌓아 올리기(Stack 'em Up)
문제 14. 에르되시 수(Erdos Numbers)
문제 15. 경시 대회 점수판(Contest Scoreboard)
문제 16. 야찌(Yahtzee)
실마리
참고

3장. 문자열
문자 코드
문자열을 표현하는 방법
프로그램 설계 예제: 회사명 변경
패턴 검색
문자열 조작
회사명 변경 프로그램
문자열 라이브러리 함수
문제 17. WERTYU
문제 18. 월도르프를 찾아라(Where's Waldorf?)
문제 19. 공통된 변경 문자열(Common Permutation)
문제 20. 암호 깨기 II(Crypt Kicker II)
문제 21. 자동 심사 스크립트(Automated Judge Script)
문제 22. 파일 조각(File Fragmentation)
문제 23. 더블릿(Doublets)
문제 24. Fmt
실마리
참고

4장. 정렬
정렬 응용 방법
정렬 알고리즘
프로그램 설계 예제: 필드 순위 매기기
정렬 라이브러리 함수
필드 순위 매기기
문제 25. 비토와 친척들(Vito's Family)
문제 26. 팬 케이크(Stacks of Flapjacks)
문제 27. 다리(Bridge)
문제 28. 낮잠 오래 자기(Longest Nap)
문제 29. 구두 수선공 문제(Shoemaker's Problem)
문제 30. CDVII
문제 31. 셸 정렬(ShellSort)
문제 32. 축구(Football(aka Soccer))
실마리
참고

5장. 계산과 대수
기계 계산
1. 정수 라이브러리
고정도 정수
고정도 계산법
진법
실수
1. 실수 처리법
2. 분수
3. 소수점
대수
1. 다항식 처리법
2. 근을 구하는 방법
로그
실수 관련 수학 라이브러리
문제 33. 자리 올림(Primary Arithmetic)
문제 34. 뒤집어서 더하기(Reverse and Add)
문제 35. 고고학자의 딜레마(The Archeologist's Dilemma)
문제 36. 1의 개수(Ones)
문제 37. 곱하기 게임(A Multiplication Game)
문제 38. 다항식의 계수(Polynomial Coefficients)
문제 39. 스턴-브로콧 수체계(The Stern-Brocot Number System)
문제 40. 모든 쌍의 합(Pairsumonious Numbers)
실마리
참고

6장. 조합론
기초적인 셈 기법
점화관계
이항계수
다른 셈 수열
재귀호출과 귀납법
문제 41. 피보나치 수의 개수(How many Fibs?)
문제 42. 땅 나누기(How Many Pieces of Land?)
문제 43. 셈(Counting)
문제 44. 표현식(Expressions)
문제 45. 완전 트리 레이블링(Complete Tree Labeling)
문제 46. 수도사 수학자(The Priest Mathematician)
문제 47. 자기기술 수열(Self-describing Sequence)
문제 48. 단계(Steps)
실마리
참고

7장. 정수론
소수
1. 소수 찾기
2. 소수의 개수
나눗셈
1. 최대공약수
2. 최소공배수
모듈러 계산
합동
1. 합동에 관한 연산
2. 일차합동의 해
3. 디오판토스 방정식
정수론 라이브러리
문제 49. 빛, 더 많은 빛(Light, More Light)
문제 50. 카마이클 수(Carmichael Numbers)
문제 51. 유클리드 문제(Euclid Problem)
문제 52. 팩토리얼 나누기(Factovisors)
문제 53. 소수 네 개의 합(Summation of Four Primes)
문제 54. 스미스 수(Smith Numbers)
문제 55. 유리 구슬(Marbles)
문제 56. 재포장(Repackaging)
실마리
참고

8장. 백트래킹
백트래킹이란
모든 부분집합 구하기
모든 순열 구하기
프로그램 설계 예제: 여덟 개의 퀸 문제
검색 가지치기
문제 57. 작은 비숍(Little Bishops)
문제 58. 15-퍼즐 문제(15-Puzzle Problem)
문제 59. 줄(Queue)
문제 60. 서비스 센터(Servicing Stations)
문제 61. 줄다리기(Tug of War)
문제 62. 에덴동산(Garden of Eden)
문제 63. 컬러 해시(Color Hash)
문제 64. 더 큰 사각형(Bigger Square Please)
실마리
참고

9장 그래프 순회
그래프의 종류
그래프 관련 자료 구조
그래프 순회: 너비 우선 순회
1. 너비 우선 검색
2. 순회 점검
3. 경로를 찾는 방법
그래프 순회: 깊이 우선 순회
1. 사이클을 찾는 방법
2. 연결 성분
위상 정렬
문제 65. 두 색으로 칠하기(Bicoloring)
문제 66. 원판 돌리기(Playing With Wheels)
문제 67. 여행자 가이드(The Tourist Guide)
문제 68. 슬래시 미로(Slash Maze)
문제 69. 편집 단계 사다리(Edit Step Ladders)
문제 70. 정육면체 탑(Tower of Cubes)
문제 71. 황혼에서 새벽까지(From Dusk Till Dawn)
문제 72. 하노이의 탑 문제 다시 보기(Hanoi Tower Troubles Again!)
실마리

10장. 그래프 알고리즘
그래프 이론
1. 차수 속성
2. 연결성
3. 그래프의 사이클
4. 평면 그래프
최소 신장 트리
최단 경로
1. 다익스트라 알고리즘
2. 전쌍 최단 경로
네트워크 흐름과 이분 매칭
문제 73. 주근깨(Freckles)
문제 74. 목걸이(The Necklace)
문제 75. 소방서(Fire Station)
문제 76. 철로(Railroads)
문제 77. 전쟁(War)
문제 78. 여행자 가이드(Tourist Guide)
문제 79. 대만찬(The Grand Dinner)
문제 80. 문제 출제 문제(The Problem With the Problem Setter)
실마리

11장. 동적 프로그래밍
탐욕 알고리즘은 그만
편집 거리
경로 재구성
편집 거리 응용
프로그램 설계 예제: 엘리베이터 최적화
문제 81. 큰 것이 똑똑하다?(Is Bigger Smarter?)
문제 82. 서로 다른 부분열(Distinct Subsequences)
문제 83. 거북이 쌓기(Weights and Measures)
문제 84. 단방향 TSP(Unidirectional TSP)
문제 85. 막대 자르기(Cutting Sticks)
문제 86. 페리 탑승(Ferry Loading)
문제 87. 젓가락(Chopsticks)
문제 88. 여행: 제4부(Adventures in Moving: Part IV)
실마리
참고

12장. 격자
수직 격자
1. 순회
2. 쌍대 그래프와 표현법
삼각, 육각 격자
1. 삼각 격자
2. 육각 격자
프로그램 설계 예: 접시 무게
원 포장법
경도와 위도
문제 89. 체스판 위의 개미(Ant on a Chessboard)
문제 90. 외발자전거(Monocycle)
문제 91. 별(Star)
문제 92. 꿀벌 마야(Bee Maja)
문제 93. 강도(Robbery)
문제 94. 2, 3, 4차원 정사각형/직사각형/정육면체/육면체((2/3/4)-D Sqr/Rects/Cubes/Boxes?)
문제 95. 더뮤바 삼각지대(Dermuba Triangle)
문제 96. 항공노선(Airlines)
실마리

13장. 기하
직선
삼각형과 삼각함수
1. 직각삼각형과 피타고라스 정리
2. 삼각함수
3. 삼각형 풀기
원
프로그램 설계 예제: 총알보다 빠르게
삼각함수 라이브러리
문제 97. 개와 땅다람쥐(Dog and Gopher)
문제 98. 밧줄나라의 밧줄 파동(Rope Crisis in Ropeland!)
문제 99. 원탁의 기사(The Knights of the Round Table)
문제 100. 초코칩 쿠키(Chocolate Chip Cookies)
문제 101. 생일 케이크(Birthday Cake)
문제 102. 최대/최소 상자(The Largest/Smallest Box)
문제 103. 적분?(Is This Integration?)
문제 104. 얼마나 클까?(How Big Is It?)
실마리

14장. 계산기하
선분과 교차
다각형과 각도 계산
최소 볼록 집합
삼각형으로 쪼개기: 알고리즘 및 관련 문제
1. 반 고흐 알고리즘
2. 넓이 계산
3. 점의 위치
격자 관련 알고리즘
1. 범위 질의
2. 격자 다각형 및 픽의 정리
기하 라이브러리
문제 105. 신입생 관리(Herding Frosh)
문제 106. 가장 가까운 두 지점(The Closest Pair Problem)
문제 107. 전기톱 학살사건(Chainsaw Massacre)
문제 108. 뜨겁워 차갑워 게임(Hotter Colder)
문제 109. Useless Tile Packers
문제 110. 레이더 추적(Radar Tracking)
문제 111. 섬과 나무(Trees on My Island)
문제 112. 우유(Nice Milk)
실마리

부록
ACM 국제 대학생 프로그래밍 경시대회
1. 준비 방법
2. 전략과 전술
국제 정보 올림피아드
1. 참가 방법
2. 형식
3. 준비 방법
탑코더 경시 대회
대학원
문제 출제자 명단

참고문헌
해답편
찾아보기