확장메뉴
주요메뉴


닫기
사이즈 비교
소득공제 강력추천
Programming Challenges

Programming Challenges

: 알고리즘 트레이닝 북

리뷰 총점7.7 리뷰 7건
베스트
IT 모바일 top100 22주
정가
26,000
판매가
23,400 (10% 할인)
구매 시 참고사항
분철서비스 시작 시 알려드립니다. 분철서비스 알림신청

품목정보

품목정보
발행일 2004년 07월 16일
쪽수, 무게, 크기 672쪽 | 1277g | 188*254*35mm
ISBN13 9788979142884
ISBN10 8979142889

책소개 책소개 보이기/감추기

목차 목차 보이기/감추기

책 속으로 책속으로 보이기/감추기

교수들은 각종 업무와 약속으로 가득 찬 복잡한 스케줄 속에서 매우 바쁘게 살아간다. 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는 행 번호를 나타낸다. 두 정수 사이에는 스페이스가 한 개 들어간다.
입력 예 출력 예
8 2 3
20 5 4
25 1 5
0


[문제 89 해답] 체스판 위의 개미(Ant on a Chessboard)
N이 매우 크기 때문에, 1부터 차례대로 수를 배열에 넣은 뒤 검색해서 위치를 찾는 방법은 사용할 수 없다. 그렇다면 어떤 방법을 사용해야 할까? 셀을 순회하는 방식을 보고, 식으로 위치를 바로 구하는 방법을 찾아야 한다.문제에 주어진 배열을 보면, 1~4까지는 크기 2짜리 정사각형을 이루는데, 5~9까지를 추가하면 크기 3의 정사각형이 된다는 것을 알 수 있다.즉, 1~n^2까지의 n^2개의 숫자로는 크기 n짜리 정사각형을 만들 수 있는 것이다.이렇게 숫자의 크기를 보고 이 수가 어떤 크기의 정사각형의 외곽선을 이루는지를 알 수 있다. 그 외곽선에서의 정확한 위치는 직접 순회를 하거나, 모범답안에서 처럼 식으로 해결할 수 있다.

/* @BEGIN_OF_SOURCE_CODE */

/* @JUDGE_ID: 46288WZ 10161 C "non-loop calculation" */

#include
#include

void main()
{
while (1)
{
long n = 0;
/* inner_box_size : 격자에서 완전히 순회한 줄의 수 */
/* step_num : 마지막 줄에서 순회한 칸의 수 */
/* step_num_from_left : 마지막 줄에서, 왼쪽부터 센 칸의 수 */
long inner_box_size, step_num, step_num_from_left;
/* column, row : 결과로 출력할 행과 열 번호 */
/* 모서리를 지났느냐에 따라서 식이 달라진다. */
long column = 0, row = 0;

scanf("%d", &n);
if ( n == 0 ) break;

inner_box_size = (long)(sqrt(n - 1));
step_num = n - inner_box_size * inner_box_size;
step_num_from_left = step_num;

if ( inner_box_size % 2 == 0 )
step_num_from_left = inner_box_size * 2 + 2 - step_num;

if ( step_num_from_left <= inner_box_size + 1 )
{
column = step_num_from_left;
row = inner_box_size + 1;
}
else
{
column = inner_box_size + 1;
row = inner_box_size * 2 + 2 - step_num_from_left;
}

printf("%ld %ld\n", column, row);
}
}

/* @END_OF_SOURCE_CODE */
문제 해답

출판사 리뷰 출판사 리뷰 보이기/감추기

추천평 추천평 보이기/감추기

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

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

회원리뷰 (5건) 회원리뷰 이동

한줄평 (2건) 한줄평 이동

총 평점 9.0점 9.0 / 10.0

배송/반품/교환 안내

배송 안내
반품/교환 안내에 대한 내용입니다.
배송 구분 예스24 배송
  •  배송비 : 무료배송
포장 안내

안전하고 정확한 포장을 위해 CCTV를 설치하여 운영하고 있습니다.

고객님께 배송되는 모든 상품을 CCTV로 녹화하고 있으며, 철저한 모니터링을 통해 작업 과정에 문제가 없도록 최선을 다 하겠습니다.

목적 : 안전한 포장 관리
촬영범위 : 박스 포장 작업

  • 포장안내1
  • 포장안내2
  • 포장안내3
  • 포장안내4
반품/교환 안내

상품 설명에 반품/교환과 관련한 안내가 있는경우 아래 내용보다 우선합니다. (업체 사정에 따라 달라질 수 있습니다)

반품/교환 안내에 대한 내용입니다.
반품/교환 방법
  •  고객만족센터(1544-3800), 중고샵(1566-4295)
  •  판매자 배송 상품은 판매자와 반품/교환이 협의된 상품에 한해 가능합니다.
반품/교환 가능기간
  •  출고 완료 후 10일 이내의 주문 상품
  •  디지털 콘텐츠인 eBook의 경우 구매 후 7일 이내의 상품
  •  중고상품의 경우 출고 완료일로부터 6일 이내의 상품 (구매확정 전 상태)
반품/교환 비용
  •  고객의 단순변심 및 착오구매일 경우 상품 반송비용은 고객 부담임
  •  직수입양서/직수입일서중 일부는 변심 또는 착오로 취소시 해외주문취소수수료 20%를 부과할수 있음

    단, 아래의 주문/취소 조건인 경우, 취소 수수료 면제

    •  오늘 00시 ~ 06시 30분 주문을 오늘 오전 06시 30분 이전에 취소
    •  오늘 06시 30분 이후 주문을 익일 오전 06시 30분 이전에 취소
  •  직수입 음반/영상물/기프트 중 일부는 변심 또는 착오로 취소 시 해외주문취소수수료 30%를 부과할 수 있음

    단, 당일 00시~13시 사이의 주문은 취소 수수료 면제

  •  박스 포장은 택배 배송이 가능한 규격과 무게를 준수하며, 고객의 단순변심 및 착오구매일 경우 상품의 반송비용은 박스 당 부과됩니다.
반품/교환 불가사유
  •  소비자의 책임 있는 사유로 상품 등이 손실 또는 훼손된 경우
  •  소비자의 사용, 포장 개봉에 의해 상품 등의 가치가 현저히 감소한 경우 : 예) 화장품, 식품, 가전제품, 전자책 단말기 등
  •  복제가 가능한 상품 등의 포장을 훼손한 경우 : 예) CD/LP, DVD/Blu-ray, 소프트웨어, 만화책, 잡지, 영상 화보집
  •  소비자의 요청에 따라 개별적으로 주문 제작되는 상품의 경우
  •  디지털 컨텐츠인 eBook, 오디오북 등을 1회 이상 다운로드를 받았을 경우
  •  eBook 대여 상품은 대여 기간이 종료 되거나, 2회 이상 대여 했을 경우 취소 불가
  •  중고상품이 구매확정(자동 구매확정은 출고완료일로부터 7일)된 경우
  •  LP상품의 재생 불량 원인이 기기의 사양 및 문제인 경우 (All-in-One 일체형 일부 보급형 오디오 모델 사용 등)
  •  시간의 경과에 의해 재판매가 곤란한 정도로 가치가 현저히 감소한 경우
  •  전자상거래 등에서의 소비자보호에 관한 법률이 정하는 소비자 청약철회 제한 내용에 해당되는 경우
소비자 피해보상
  •  상품의 불량에 의한 반품, 교환, A/S, 환불, 품질보증 및 피해보상 등에 관한 사항은 소비자분쟁해결기준(공정거래위원회 고시)에 준하여 처리됨
환불 지연에
따른 배상
  •  대금 환불 및 환불 지연에 따른 배상금 지급 조건, 절차 등은 전자상거래 등에서의 소비자 보호에 관한 법률에 따라 처리
  • 절판 상태입니다.
뒤로 앞으로 맨위로 공유하기