(NAMGUNGEUN)

알고리즘 트레이닝 북 PROGRAMMING CHALLENGES

한신학 han theology 2017. 12. 12. 19:32

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

[인터넷 교보문고 제공]

 

저자소개

스티븐 스키에나

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위 입상
-. 현재 서울대학교 휴학 후 병역특례로 근무 중

[강컴닷컴 제공]

목차

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. 준비 방법 
탑코더 경시 대회 
대학원 
문제 출제자 명단 

참고문헌 
해답편 
찾아보기

[예스24 제공]

이 책의 원서·번역서

(1권)

출판사 서평

프로그래밍 스킬은 연습을 통해서만 향상된다 

프로그래밍적 상상력을 극대화하는 112가지 유형의 알고리즘과 자료구조


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

[예스24 제공]

책속으로

교수들은 각종 업무와 약속으로 가득 찬 복잡한 스케줄 속에서 매우 바쁘게 살아간다. P 교수는 낮잠을 자는 것을 좋아하지만 스케줄이 바쁘다 보니 낮잠을 잘 수 있는 시간이 별로 없다. 하지만 P 교수는 매일 한 번씩은 낮잠을 자고 싶어한다. 물론 그의 스케줄을 감안해서 될 수 있으면 오랫동안 낮잠을 즐길 수 있는 방법을 찾아야 한다. P 교수가 최대한 오랫동안 낮잠을 잘 수 있게 해주는 프로그램을 만들어라
- 본문의 "낮잠 오래 자기(Longest Nap)" 문제 중에서 -


블라디미르는 새하얀 피부와 날카로운 이를 가지고 있다. 나이는 600살이나 되지만, 뱀파이어인 블라디미르에게 나이는 별 의미가 없다. 블라디미르는 뱀파이어로 살아가는 데 있어서 별 다른 불편함을 느끼지 못한다. 그는 항상 야간 근무를 맡는 의사로 일하고 있는데, 훌륭하게 의사 생활을 하고 있으며, 야간 근무를 도맡아 하다 보니 동료들하고도 매우 사이 좋게 지내고 있다. 그는 파티장에서 맛을 보는 것만으로도 혈액형을 알아맞히는 쇼를 보여주곤 한다. 블라디미르는 여행을 하고 싶은데, 뱀파이어이다 보니 세 가지 문제를 극복해야만 한다.

1. 항상 관을 가지고 다녀야 하기 때문에 기차 여행 밖에는 할 수가 없다. 다행히도 워낙 오랫동안 돈을 모았기 때문에 재력이 상당하므로 항상 1등칸을 타고 다닐 수 있다.
2. 황혼에서 새벽까지만, 즉 오후 여섯 시부터 오전 여섯 시까지만 여행할 수 있다. 낮에는 기차역을 벗어날 수 없다.
3. 뭔가 먹을 것을 가지고 다녀야 한다. 하루에 피를 1리터씩 먹어야 하며, 그의 관 안에서 정오(낮 12시)에 피를 마신다.

두 도시가 주어졌을 때 최단 경로를 찾는 프로그램을 만들어서 블라디미르가 최소한의 피만 챙겨서 여행할 수 있도록 도와주자. 피를 너무 많이 가지고 다니면 사람들이 "그 피 가지고 뭘 하실 건가요?" 같은 질문을 하면서 의심할 수도 있기 때문이다.
- "황혼에서 새벽까지(From Dusk Till Dawn)" 문제 중에서 - 본문

[문제 28] 낮잠 오래 자기(Longest Nap)
PC/UVa ID: 110404/10191, 인기도: B, 성공률: 보통, 레벨: 1
교수들은 각종 업무와 약속으로 가득 찬 복잡한 스케줄 속에서 매우 바쁘게 살아간다. P 교수는 낮잠을 자는 것을 좋아하지만 스케줄이 바쁘다 보니 낮잠을 잘 수 있는 시간이 별로 없다. 하지만 P 교수는 매일 한 번씩은 낮잠을 자고 싶어한다. 물론 그의 스케줄을 감안해서 될 수 있으면 오랫동안 낮잠을 즐길 수 있는 방법을 찾아야 한다. P 교수가 최대한 오랫동안 낮잠을 잘 수 있게 해주는 프로그램을 만들어라.
입력
임의 개수의 테스트 케이스가 입력되며 각 테스트 케이스가 하루를 나타낸다. 각 테스트 케이스의 첫번째 줄에는 100 이하의 양의 정수 s가 들어있으며 이 수는 그 날 미리 잡혀있는 약속의 개수를 나타낸다. 그 다음 줄부터 s개의 줄에는 time1 time2 약속 형식으로 잡혀있는 약속이 입력되며, time1은 시작 시각, time2는 끝나는 시각을 나타낸다. 모든 시각은 hh:mm 형식으로 주어진다. 끝나는 시각은 반드시 시작 시간보다 뒤며 시작 시간과 스페이스 한 개로 구분된다.

모든 시각은 10:00 이후, 18:00 이전으로 주어진다. 따라서 결과도 반드시 이 시간 내에 있어야 한다. 즉 10:00 전에 낮잠을 잘 수 없고 18:00 넘어서까지 낮잠을 잘 수도 없다.

약속은 임의의 문자를 열거한 형태로 주어지는데 반드시 한 줄에 입력되어야 한다. 각 줄의 길이는 255 글자를 넘지 않으며 10≤hh≤18, 0≤mm<60이라고 가정할 수 있다. 하지만 약속이 어떤 정해진 순서대로 입력된다고 가정할 수 없고 파일 종료 문자가 나올 때까지 입력을 모두 읽어야 한다.
출력
각 테스트 케이스에 대해 다음과 같은 내용을 한 줄씩 출력한다.

Day #d: the longest nap starts at hh:mm and will last for [H0 hours and] M minutes.

d는 테스트 케이스 번호(1에서 시작)를, hh:mm은 낮잠을 자기 시작하는 시각을 의미한다. 낮잠 자는 시간을 표시할 때는 다음과 같은 규칙을 따른다.

1. 총 시간 X가 60분 미만이면 "X minutes"만 출력한다.
2. 총 시간 X가 60분 이상이면 "H hours and M minutes"라고 출력한다. 이때 H는 다음과 같이 결정된다.
H=X÷60(정수 나눗셈), M=X를 60으로 나눈 나머지
단수, 복수는 따지지 않는다. 즉 "1 minutes", "1 hours" 같은 식으로 출력되도록 해야 한다.

낮잠을 잘 수 있는 시간은 시작 시각과 끝나는 시각의 차로 계산한다. 즉 약속이 14:00에 끝나고 다음 약속이 14:47에 시작하면 14:47-14:00=47분 동안 낮잠을 잘 수 있다.

가장 길게 낮잠을 잘 수 있는 시간이 여러 개 있으면 그 중 가장 빨리 시작하는 것을 출력한다. 낮잠을 잘 시간이 전혀 없을 정도로 교수가 하루 종일 바쁜 경우는 없다고 가정한다.
입력 예
4
10:00 12:00 Lectures
12:00 13:00 Lunch, like always.
13:00 15:00 Boring lectures...
15:30 17:45 Reading
4
10:00 12:00 Lectures
12:00 13:00 Lunch, just lunch.
13:00 15:00 Lectures, lectures... oh, no!
16:45 17:45 Reading (to be or not to be?)
4
10:00 12:00 Lectures, as everyday.
12:00 13:00 Lunch, again!!!
13:00 15:00 Lectures, more lectures!
15:30 17:15 Reading (I love reading, but should I schedule it?)
1
12:00 13:00 I love lunch! Have you ever noticed it? :)
출력 예
Day #1: the longest nap starts at 15:00 and will last for 30 minutes.
Day #2: the longest nap starts at 15:00 and will last for 1 hours and 45 minutes.
Day #3: the longest nap starts at 17:15 and will last for 45 minutes.
Day #4: the longest nap starts at 13:00 and will last for 5 hours and 0 minutes.
[문제 28 해답] 낮잠 오래 자기(Longest Nap)
약속 시간들을 정렬한 다음, 앞에서부터 읽어 나가면서 중간에 비는 시간을 계산하여 그 최대 값을 찾으면 된다. 시간 계산을 편리하게 하기 위해, 입력 받은 시간 값을 10시 정각을 기준으로 하여 몇 분이 지났는지로 변환해서 처리했다.

/* @BEGIN_OF_SOURCE_CODE */

/* @JUDGE_ID: hoimann 10152 C "simple one" */

#include 
#include 

#define MAX_APPTS 100

typedef struct {
int start, end;
} appointment;

int str2time(char *hh, char *mm)
{
return (hh[1] - '0') * 60 + (mm[0] - '0') * 10 + (mm[1] - '0');
}

appointment appt[MAX_APPTS + 2];
char line[256];

void main()
{
int num_appts;
int day_number, i, j, min, nap_slot, nap_time;
appointment temp_appt;

day_number = 0;
while (scanf("%d", &num_appts) == 1) {
day_number++;
gets(line);
appt[0].start = 0;
appt[0].end = 0;
appt[num_appts + 1].start = 8 * 60;
appt[num_appts + 1].end = 8 * 60;
for (i = 1; i <= num_appts; i++) {
gets(line);
appt[i].start = str2time(line, line + 3);
appt[i].end = str2time(line + 6, line + 9);
}
for (i = 1; i < num_appts; i++) {
min = i;
for (j = i; j <= num_appts; j++)
if (appt[j].start < appt[min].start)
min = j;
temp_appt = appt[i];
appt[i] = appt[min];
appt[min] = temp_appt;
}
nap_slot = 0;
nap_time = appt[1].start - appt[0].end;
for (i = 1; i <= num_appts; i++)
if (appt[i + 1].start - appt[i].end > nap_time) {
nap_slot = i;
nap_time = appt[i + 1].start - appt[i].end;
}
printf("Day #%d: the longest nap starts at ", day_number);
printf("1%d:%02d and will last for ",
appt[nap_slot].end / 60,
appt[nap_slot].end % 60);
if (nap_time >= 60)
printf("%d hours and %d minutes.\n", nap_time / 60, nap_time % 60);
else
printf("%d minutes.\n", nap_time);
}
}

/* @END_OF_SOURCE_CODE */


[문제 89] 체스판 위의 개미(Ant on a Chessboard)
PC/UVa ID: 111201/10161, 인기도: B, 성공률: 높음, 레벨: 1
어느 날 앨리스라는 개미가 M×M 체스판에 올라갔다. 앨리스는 체스판에 있는 모든 셀을 방문하려고 한다. 그래서 판 한 쪽 구석에서 시작해서 체스판을 한 꺼풀씩 훑어나가기로 했다.

앨리스는 (1, 1)자리부터 움직이기 시작했다. 처음에는 한 칸 위로 올라간 다음, 오른쪽으로 한 칸 이동하고, 다시 한 칸 아래로 내려왔다. 그리고 나서 한 칸 오른쪽으로 움직여서 두 칸 위로 올라가고, 두 칸 왼쪽으로 움직였다. 이런 식으로 매번 한 행, 그리고 한 열씩을 더 움직였다.

예를 들어 앨리스가 25단계를 움직인 경로를 표시해보면 다음과 같다. 여기에서 각 숫자는 앨리스가 각 셀을 방문한 순서를 나타낸다.

25 24 23 22 21
10 11 12 13 20
9 8 7 14 19
2 3 6 15 18
1 4 5 16 17

앨리스는 여덟 번째 단계에서는 (2, 3) 위치에 있었고, 20번째 단계에서는 (5, 4) 위치에 있었다. 단계 수가 주어졌을 때, 체스판이 매우 커서 움직일 수 있는 위치에 제한이 없다고 할 때, 앨리스의 위치를 결정하는 프로그램을 만들어야 한다.
입력
입력 파일은 여러 줄로 구성되는데, 각 줄마다 단계 번호를 나타내는 정수 N(1≤N≤2×109)이 하나씩 입력된다. 0이 입력되면 입력이 종료된다.
출력
입력된 값에 대해 해당 단계에서의 앨리스의 위치 (x, y)를 나타내는 두 정수를 출력한다. x는 열 번호, y는 행 번호를 나타낸다. 두 정수 사이에는 스페이스가 한 개 들어간다.
입력 ? 

[예스24 제공]

추천평

프로그램은 프로그래밍 언어를 단순히 문법에 맞게 늘어놓은 것 같지만 프로그래머의 사고의 구조가 그대로 투영된 결과물이다. 못쓴 글씨를 남에게 내놓기 부끄럽듯이 엉성한 프로그램은 프로그래머의 지적 구조를 드러내 보이는 사진 건판 같은 것이다. 프로그램을 보면 프로그래머의 도피성 땜질도 볼 수 있고 예술가의 자부심 같은 것도 느낄 수 있다.

프로그래밍 컨테스트는 프로그래밍을 얼마나 잘 하느냐를 테스트하겠다는 것인데 이것은 일반이 생각하는 것처럼 특정 프로그래밍 언어를 잘 사용하는 것과는 별개의 문제다. 프로그래밍 컨테스트는 문제 해결 능력을 테스트하는 것이다. 그래서 문제들은 대개 고도의 수학적, 체계적 사고를 요한다. 대학의 컴퓨터학과에서 배우는 이론 과목인 컴퓨터 알고리즘이 이 부분에 가장 관련이 깊다.
문병로 교수 추천사 중에서(서울대학교 컴퓨터공학부 부교수)

[예스24 제공]

네티즌 리뷰

(5건)