지식의힘!! [강컴]

Home >

Programming Challenges : 알고리즘 트레이닝 북

지은이 스티븐 스키에나 외 | 출판사 한빛미디어 | 발행일 2004년 07월 16일

	판매가	26,000원 → 19,240원 26%
	마일리지	8% 1,540원

	발행일	2004-07-16
	ISBN	8979142889 \| 9788979142884
	기타정보	번역서 \| 672쪽

	예상출고일	금일 가능 (근무일기준)
	배송비	2,000원 (20,000원이상 무료배송)

컴퓨터공학

종합지수 37p 11 위

월간지수 30p 7 위

주간지수 6p 17 위

※ 네이버 체크아웃으로 구매시 비회원으로 구매가
됨으로 강컴 마일리지는 적립 되지 않습니다.

	이 책의 원서
		Programming Challenges SPRINGER-VERLAG \| Steven S. Skiena

컴퓨터공학 분야 베스트(월)

1.	생각하는 프로그래밍[재출간판]
2.	Introduction to Algorithms (개정판) (2007년 대한민국학술원 우수학술도서)
3.	뇌를 자극하는 알고리즘

컴퓨터공학 분야 베스트(주)

1.	CODE COMPLETE 2/E
2.	생각하는 프로그래밍[재출간판]
3.	Refactoring (한글판)

컴퓨터공학 분야 신간

1.	Motion Analysis and Image Sequence Processing
2.	Xilinx 6.3 Student Edition
3.	VLSI Artificial Neural Networks Engineering

프로그래밍 경시 대회를 준비하기 위한 프로그래밍 연습교재. ACM 국제 대학생 프로그래밍 경시대회와 국제 정보 올림피아드, 탑코더 경시 대회 등의 유명한 국제 프로그래밍 경시대회에 대비하여 알고리즘과 코딩 기법의 이론과 그 연습문제를 다루고 있다.

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. 에르되시 수(Erd?s 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. 준비 방법
탑코더 경시 대회
대학원
문제 출제자 명단

참고문헌
해답편
찾아보기

Steven S. Skiena
SUNY 스토니 브룩 전산학과 교수로, 『Algorithm Design Manual』을 비롯한 여러 책의 저자이기도 하다. 2001년에는 IEEE 컴퓨터 분과에서 학부 강의상을 수상했다.

Miguel A. Revilla
스페인 바야돌리드 대학교 응용수학과 교수다. ACM ICPC의 공식 웹사이트 아카이브 담당자며, 로봇 심사위원 및 경시 대회 호스팅 웹사이트를 운영하고 있다.

[역자 소개]

서환수(hssuh@csns.snu.ac.kr)
서울대학교 물리학부를 졸업하고 현재 서울대학교 물리학부 대학원에 재학중이다. 『펄로 배우는 알고리즘(Mastering Algorithms with Perl)』(한빛미디어, 2000), 『제대로 배우는 자바 2(Learning Java)』(한빛미디어,2001), 『창시자 게리 그로스먼과 함께 배우는 플래시 액션 스크립트(ActionScript: The Definitive Guide)』(한빛미디어, 2002), 『MySQL 시스템 관리와 프로그래밍(Managing & Using MySQL)』(한빛미디어, 2002), 『정규 표현식 완전 해부와 실습(Mastering Regular Expressions)』(한빛미디어, 2003), 『Head First Java : 뇌 회로를 자극하는 자바 학습법(Head First Java)』(한빛미디어, 2004) 등을 번역했다.

[모범 답안 제공]
김강회(kanghoe@bawi.org)
-. KAIST 전산학과 졸업, 코넬 대학(Cornell Univ.) 전산학과 박사 과정 수료
-. 국제 정보 올림피아드 은상 수상, 현대전자 소프트웨어 경진대회 대상, ACM-ICPC 10위 입상
-. 국제 정보 올림피아드 한국 대표단 부단장 역임
-. 역서: 『C# 프로그래밍 개정판(Programming C#)』(한빛미디어, 2003), 『프로그래밍 입문자를 위한 C#(Learning C#)』(한빛미디어, 2003)
-. 현재 (주)티맥스소프트에 재직 중

동규환(rubyeye@kaist.ac.kr)
-. 1999년 한국정보올림피아드(KOI) 금상 수상
-. 2000년 한국정보올림피아드(KOI) 은상 수상
-. 2001년 한국정보올림피아드(KOI) 동상 수상
-. 2001년 국제정보올림피아드(IOI) 후보 선발
-. 2003년 ACM-ICPC 7위 입상
-. 현재 카이스트 학과 3학년에 재학 중

유승현(heuristic84@hotmail.com)
-. 1999년 한국정보올림피아드(KOI) 대상 수상
-. 1999년, 2000년 국제정보올림피아드(IOI) 후보 선발
-. 2001년 한국정보올림피아드(KOI) 대상 수상
-. 2003년 ACM-ICPC 아시아지역 서울 대회 7위 입상
-. 현재 카이스트 전자전산학과 재학 중

유원석(ainu7@naver.com)
-. 1996년 국제정보올림피아드(IOI) 금상 수상
-. 1997년 국제정보올림피아드(IOI) 동상 수상
-. 1998년 국제정보올림피아드(IOI) 은상 수상
-. 2001-2002년 ACM-ICPC 아시아지역 대전 대회 1위 입상
-. 2001-2002년 ACM World Final 11위 입상
-. 현재 서울대학교 휴학 후 병역특례로 근무 중