제목: 프로그래밍 콘테스트 챌린징
지은이:Takuya Akiba, Yoichi Iwata, Masatoshi Kitagawa
옮긴이: 박건태, 김승엽
페이지: 448
판형: 4x6배변형(188x235)
도수: 1도
정가: 25,000원
발행일: 2011년 10월 24일
ISBN: 978-89-966598-4-6
[절판된 도서입니다!!]
[강컴] [교보] [리브로] [반디] [11번가] [알라딘] [예스24] [인터파크]
_도서 내용
국제/국내 프로그래밍 콘테스트를 준비하기 위한 책입니다. 하지만 프로그래머가 되고자 하는 학생이나 프로그래머도 "프로그래밍 뇌"를 강화하기 위해 학습할 수 있는 내용입니다.
문제들은 그렇게 어렵지는 않습니다. 주어지는 입력이 단순하기 때문에 손으로 그림을 그려가면서 풀어보면 대부분 풀리는 문제들입니다. 하지만, 이것을 (주어진 제한조건하에) 일반화하기 위해서는 상당히 많은 알고리즘 지식이 필요합니다. 바로 이러한 알고리즘을 제한 시간과 제한 조건에 맞게 프로그래밍할 수 있도록 도와주는 책입니다.
_대상 독자
프로그래머가 되고자 하는 학생
각종 프로그래밍 경시대회를 준비하는 학생
‘프로그래밍 뇌’가 조금씩 작아지고 있다고 생각하는 프로그래머
알고리즘 면접을 보는 국제/국내 유수의 IT 기업 취업을 준비하고 있는 예비 프로그래머
_목차
CHAPTER 1 프로그래밍 콘테스트 (초급편)
1-1 프로그래밍 콘테스트란 무엇인가요?
1-2 어떤 콘테스트가 있나요?
세계적인 규모의 콘테스트 - Google Code Jam(GCJ)
상위 랭크를 목표로! - TopCoder
역사 깊은 콘테스트 - ACM/ICPC
중학생, 고등학생을 위한 정보 올림피아드 - KOI/IOI
웹에서 자동 채점 - online judge
1-3 이 책은?
다루는 내용
사용하는 언어
문제를 다루는 방법
프로그램은
이 책을 다 읽은 후
1-4 어떻게 해답을 제출하나요?
POJ에 제출하는 방법
GCJ에 제출하는 방법
1-5 효율적인 알고리즘을 목표로!
계산량이란?
실행시간이란?
1-6 가볍게 워밍업
먼저 간단한 문제부터
POJ 문제 [Ants]
허들이 높아진 [제비 뽑기]
_주요 내용
최고의 알고리즘을 찾을 때까지 당신의 뇌를 뛰게 하라!
극한의 알고리즘 트레이닝, 최고의 프로그래머를 꿈꾼다!
문제
해결 능력을 겨룬다!
성능, 문제 해결, 아이디어 등을 겨루는 다양한 프로그래밍 콘테스트(경시대회)가 있습니다. 이 책은 그 중에서 문제 해결을 겨루는 콘테스트를 다룹니다.
프로그래머로서 기초체력을 튼튼히!
프로그래밍 콘테스트에서는 효율적인 알고리즘을 생각하고 정확하게 구현해야 합니다. 다양한 문제에 대해 유연한 발상이 필요하고 기초적인 알고리즘 지식을 갖추어야 합니다. 말 그대로 콘테스트 준비를 함으로써 프로그래머로서 기초체력을 튼튼히 할 수 있습니다.
‘프로그래밍 뇌’의 증강을 위해!
프로그래머가 되고자 하는 학생뿐만 아니라 현업 프로그래머도 ‘프로그래밍 뇌’의 증강을 위해 한 번쯤 도전해볼 만합니다. 자신의 알고리즘 능력을 점검해볼 수 있고 응시자와 선의의 경쟁을 통해 실력을 가늠하고 학습 모티브를 얻을 수 있습니다.
다양한 콘테스트에 대비한다!
세계적인 규모의 콘테스트: Google Code Jam(GCJ)
상위 랭크를 목표로: TopCoder
역사 깊은 콘테스트: ACM/ICPC
중학생, 고등학생을 위한 정보 올림피아드: KOI/IOI
유수 IT 기업의 면접에 대비한다!
구글, MS, 국내 유수의 IT 기업 등의 알고리즘 능력 점검을 위한 면접 시험에 대비할 수 있습니다.
_편집자 코멘트
이 책에서 주어진 문제는 눈으로 풀어도 출력값은 구할 수 있습니다. 하지만 이것을 일반화하기 위해서는 특수한 알고리즘 기법이 필요합니다. 수많은 알고리즘을 책으로 무진장 많이 학습했다고 해서 쉽게 그러한 알고리즘 기법을 떠올리지는 못하겠죠? 이 책은 바로 이론으로만 알고 있는 알고리즘 지식을 어떤 상황에서도 생각해내서 응용할 수 있게 해주는 책입니다. 물론, 간단하게 이론을 정리해서 설명해주기도 합니다.
이 책이 여러 유용한 점이 있기는 하지만, 시험만을 준비하기 위해 문제 유형과 해법을 달달 외우기만 한다면, 프로그래밍 능력에서 중요한 요소인 창의력과 끈질기게 해법에 도전하는 지구력은 결코 얻을 수 없을 것입니다.
이 책을 학습할 때 생각의 깊이를 좀더 깊게 파고 창의적 사고의 너비를 좀더 넓게 두었으면 좋겠습니다. 누구에게는 힘든 정신적 노동일 수 있고 누구에게는 뇌에서 우러나는 소리 없는 땀이 주는 맛을 크게 맛볼 수 있는 계기가 될 것으로 생각합니다. 한번 도전해보세요!
참, 알고리즘 면접을 치르는 IT 기업의 취업 준비에도 도움이 될 수 있습니다.
"최고의 알고리즘을 찾을 때까지 당신의 뇌를 뛰게 하라!"
_저자 소개
[지은이]
Takuya Akiba
1988년 출생. 2007년 동경대학 입학. 프로그래밍 콘테스트에서는 아이디 iwi로 활약 중. 주요 전적은 Topcoder Open 2009에서 9위.
Yoichi Iwata
1988년 출생. 2007년 동경대학 입학. 프로그래밍 콘테스트에서는 아이디 wata로 활약 중. 주요 전적은 Google Code Jam 2009에서 3위.
Masatoshi Kitagawa
1988년 출생. 2007년 동경대학 입학. 프로그래밍 콘테스트서는 아이디 kita_masa로 활약 중. 주요 전적은 ICPC World Finals 2010에서 16위.
[옮긴이]
박건태
시스템 프로그래머이다. 현재 클라우드 컴퓨팅(Cloud Computing)과 콘텐츠 딜리버리 네트워크(CDN) 전문기업 ㈜솔루션 박스에서 Iass 기반 Cloud를 개발 중이다. 일본에서 임베디드 리눅스 기반의 다양한 어플리케이션을 개발했고 SI 업체에서 다수의 시스템을 개발했다. MVC를 확장한 경량 프레임워크를 개발해 오픈 소스로 제공한 뒤 귀국했다.
저서 <Jlet으로 배우는 위피 프로그래밍>(한빛미디어, 2005), 역서 <Java 언어로 배우는 리팩토링 입문>(한빛미디어, 2007)이 있다.
김승엽
일본에서 시스템 프로그래머로 시작하여, 일본 기업의 임베디드 시스템 개발센터 소장직을 역임했고 한국으로 돌아와서 현재 ㈜디지털크래프트 코리아의 대표이사를 맡고 있다. 일본에서 RTOS 분야와 임베디드 컴포넌트 시스템 분야에서 활동했고 일본의 비영리 법인단체인 TOPPERS 프로젝트에서 많은 성과물을 오픈 소스로 제공하고 있다. 현재는 TOPPERS 프로젝트의 한국보급WG에서 활동하고 있다.
'신간소개' 카테고리의 다른 글
[신간소개] 빅 데이터 시대를 위한 NoSQL 핵심 가이드 (0) | 2011.12.19 |
---|---|
[신간소개] 웹 디자이너를 위한 jQuery (2) | 2011.11.15 |
[신간소개] 처음부터 다시 배우는 HTML5&CSS3: 실전 웹 표준 사이트 구축까지 (0) | 2011.09.22 |
[신간소개] 거꾸로 배우는 소프트웨어 개발 (0) | 2011.08.14 |
[신간소개] 프로그래머 그 다음 이야기 (0) | 2011.07.11 |
2011년 11월 7일 현재
-------- p.30(1째줄)_1쇄--------
오류: Lcm
수정: L cm
--------------------------------------
-------- p.31(표에서)_1쇄--------
(ChanMin Kim님 제보)
오류: 1048567
수정: 1048576
--------------------------------------
-------- p.52(15째줄)_1쇄--------
오류: d[iㄴ][j]
수정: d[i][j]
--------------------------------------
-------- p.57(아래에서 3째줄)_1쇄 --------
오류: 6(500원짜리 1개, 50원짜리 2개, 5원짜리 2개 합계 6개)
수정: 6(500원짜리 1개, 50원짜리 2개, 10원짜리 1개, 5원짜리 2개 합계 6개)
---------------------------------------------------------------------
수정:
---------------------------------------------------------------------
-------- p.71_1쇄--------
(정현환님 제보)
"동적 설계법(dynamic programming)"이라는 용어와 241페이지의 "동적 계획법"은 같은 용어입니다. "동적 계획법으로 통일합니다.
--------------------------------------
-------- p.74_1쇄----------------------------------------------------
(정현환님 제보)
memset을 이용하지 못하는 경우는 "int 배열과 같은 각 원소에 할당된 크기가 1byte보다 큰 배열일 경우다."로 좀더 구체적으로 표현하겠습니다.
----------------------------------------------------------------------
-------- p.74 & p.88_1쇄---------------------------------------------
(정현환님 제보)
74페이지의 LCS(최장 공통 부분열)은 <최장 공통 부분 서열(혹은 수열)>이라는 용어도 함께 쓰임을 알려드립니다.
88페이지의 LIS(최장 증가 부분열) 역시 <최장 증가 부분 서열>이라는 표현도 함께 쓰임을 알려드립니다.
------------------------------------------------------------
-------- p.79_1쇄(DP 테이블에서)--------------------------------------
(장원영님, 궁금님 제보)
오류: j/i
수정: i/j
----------------------------------------------------------------------
-------- p.86(마지막 소스 바로 위)_1쇄--------
(ChanMin Kim님 제보)
오류: dp[i+1][j] = (0 <= k <= m_i 그리고 k x a_i<=j에서 dp[i][j-k x a_i]가 참이 되는 k가 존재한다.
수정: dp[i+1][j] = (0 <= k <= m_i 그리고 k x a_i<=j에서) dp[i][j-k x a_i]가 참이 되는 k가 존재한다.
--------------------------------------
-------- p.86(아래 수식 바로 윗단락 2째줄)_1쇄--------
(장원영님 제보)
오류: K(>0)
수정: k(>0)
--------------------------------------
-------- p.87(마지막 수식)_1쇄--------
(ChanMin Kim님 제보)
오류: -1(j<a) 또는 dp[i+1][j-a_i]<= 0
수정: -1 (j<a_i 또는 dp[i+1][j-a_i] ≦ 0)
--------------------------------------
-------- p.100(소스 9번째줄)_1쇄--------
(ChanMin Kim님 제보)
오류: heap[i]=x;
수정: 인덴트 오류입니다. 들여쓰기가 한번 더 되어야 합니다.
--------------------------------------
-------- p.107_1쇄--------
(ChanMin Kim님 제보)
오류: p108의 bool타입의 find 함수명 부분
수정: 인덴트 오류입니다. 들여쓰기가 한칸 빠져야 합니다.
오류: p109의 마지막 else 부분
수정: 인덴트 오류입니다. 들여쓰기가 한칸 추가되어야 합니다.
--------------------------------------
-------- p.107_1쇄--------
(ChanMin Kim님 제보)
오류: 자식 노드 11과 17이 길을 잃습니다.
수정: 자식 노드 10과 17이 길을 잃습니다.
--------------------------------------
-------- p.110(소스 아래에서 5째줄, 2째줄)_1쇄--------
(ChanMin Kim님 제보)
오류: printf("%d\n", *ite); 과 return 0;
수정: 인덴트 오류입니다. 들여쓰기가 한칸 추가되어야 합니다.
--------------------------------------
-------- p.134(본문 3째줄)_1쇄--------
(ChanMin Kim님 제보)
오류: d[i]=d[i]+(i부터 j의 변(edge)의 코스트)
수정: d[j]=d[i]+(i부터 j의 변(edge)의 코스트)
--------------------------------------
-------- p.137(소스 위 2째줄)_1쇄--------
(ChanMin Kim님 제보)
오류: 음의 폐로가 있는지 없는지는 d[i][j]가
수정: 음의 폐로가 있는지 없는지는 d[i][i]가
--------------------------------------
-------- p.137(8째줄)_1쇄--------
(ChanMin Kim님 제보)
오류: d[O][i]
수정: d[0][i]
--------------------------------------
-------- p.137(13째줄)_1쇄--------
(ChanMin Kim님 제보)
오류: d[k][[i]
수정: d[k][i]
--------------------------------------
-------- p.148(3째줄)_1쇄--------
(ChanMin Kim님 제보)
오류: d[i+1]+O>=d[i]
수정: d[i+1]+0>=d[i]
--------------------------------------
-------- p.150(small과 Large 제약조건_1쇄--------
(ChanMin Kim님 제보)
오류: x_1, y_1 x_1, y_1
수정: x_i, y_i x_i, y_i
--------------------------------------
-------- p.151(아래에서 10째줄_1쇄--------
(ChanMin Kim님 제보)
오류: v_2가 내림차순으로 정렬되어 있지 않으면 y_1 < y_2 이 되는
수정: v_2가 내림차순으로 정렬되어 있지 않으면 y_i < y_j 이 되는
--------------------------------------
-------- p.154(4째줄_1쇄--------
(ChanMin Kim님 제보)
오류: 00...010...0
수정: 00...0, 10...0
--------------------------------------
-------- p.155(아래에서 5째줄_1쇄--------
(ChanMin Kim님 제보)
오류: a_1,a_2,a_Q
수정: a_1, a_2, ..., a_Q
--------------------------------------
-------- p.157(소스 중간의 for문 인덴트 오류)_1쇄--------
(ChanMin Kim님 제보)
오류: dp[q][q + 1] = 0;
수정: 들여쓰기 해야 함
--------------------------------------
-------- p.164(마지막줄)_1쇄--------
(ChanMin Kim님 제보)
오류: |y1-y2=0
수정: |y1-y2|=0
--------------------------------------
-------- p.173_1쇄--------
(정현환님 제보)
오류: 제곱승
수정: 거듭제곱
--------------------------------------
-------- p.173(아래에서 4째줄)_1쇄--------
(ChanMin Kim님 제보)
오류: Biginteger
수정: BigInteger
--------------------------------------
-------- p.178(박스안 1째줄)_1쇄--------
(ChanMin Kim님 제보)
오류: a_1 >= k
수정: a_i >= k
--------------------------------------
(ChanMin Kim님 제보)
오류 : 메모화
오류 : 지금까지 소개한 기법을 이용해서, GCJ에 의해 발전된 문제를 실제로 해결해봅시다.
오류 : 기하의 문제
수정: 기하 문제
-----------------------------------------
포제원리는 '포함-배제 원리' 라는 용어와 같습니다.
'다배장 연산(bignum arithmetic)'은 '큰수 연산(big-number arithmetic)'이라는 표현과 같습니다.
-----------------------------------------
--------계산량이라는 용어에 대해--------
"계산량은 O(X)다" 라는 표현이 많이 보이는데, 보통 big-Oh notation에 대해서는 "시간 복잡도(time complexity)"로 표기를 합니다만, 계산량이라는 용어를 일부러 계속 넣은 것은, 알고리즘 용어보다는 계산하는 양이라는 의미로 이해할 수 있도록 사용되었습니다. 시간 복잡도라고 했다면 책이 조금 무거워질 것 같아 계산량이라는 표현 그대로 사용했으니 참고 바랍니다.
-----------------------------------------------------
------------------------------------------------------
'오탈자 정보' 카테고리의 다른 글
[오탈자 정보] 빅 데이터 시대를 위한 NoSQL 핵심 가이드 (0) | 2011.12.19 |
---|---|
[오탈자 정보] 웹 디자이너를 위한 jQuery (87) | 2011.11.14 |
[오탈자 정보] 처음부터 다시 배우는 HTML5&CSS3 (63) | 2011.09.18 |
[오탈자 정보] 거꾸로 배우는 소프트웨어 개발(2011년 8월 22일 출간) (5) | 2011.08.23 |
[오탈자 정보] 프로그래머 그 다음 이야기(2011년 7월 8일 출간) (7) | 2011.07.11 |
for GCJ, TopCoder, ACM/ICPC, KOI/IOI
부제 그대로 국제/국내 프로그래밍 콘테스트를 준비하기 위한 책입니다. 현업 프로그래머도 "생각의 뇌"를 강화하기 위해 학습해볼 만하다고 생각합니다.
문제들은 그렇게 어렵지는 않습니다. 주어지는 입력이 단순하기 때문에 손으로 그림을 그려가면서 풀어보면 대부분 풀리는 문제들입니다. 하지만, 이것을 일반화하기 위해서는 (즉, 주어진 제한조건하에) 상당히 많은 알고리즘 지식이 필요합니다.
이 책이 여러 유용한 점이 있기는 하지만, 시험만을 준비하기 위해 문제유형와 해법을 달달 외우기만 한다면, 프로그래밍 능력에서 중요한 요소인 창의력과 끈질기게 해법에 도전하는 지구력은 결코 얻을 수 없을 것입니다.
이 책을 학습할 때 생각의 깊이를 좀더 깊게 파고 창의적 사고의 너비를 좀더 넓게 두었으면 좋겠습니다. 누구에게는 힘든 정신적 노동일 수 있고 누구에게는 뇌속에서 우러나는 소리없는 땀이 주는 맛을 크게 맛볼 수 있는 계기가 될 것으로 생각합니다. 한 번 도전해보세요!
다음 그림은 이 책의 예제 중 하나입니다.
보면 아시겠지만, 눈으로 풀어도 출력값은 구할 수 있습니다. 하지만, 이것을 일반화하기 위해서는 '너비우선탐색'이라는 특수한 알고리즘 기법이 필요합니다. 너비우선탐색을 알고리즘 책으로 무진장 많이 학습했다고 해서 쉽게 그러한 알고리즘 기법을 떠올리지는 못하겠죠?
이 책은 바로 이론적으로만 알고있는 알고리즘 지식을 어떤 상황에서도 생각해내서 응용할 수 있게 해주는 책입니다. 물론, 간단하게 이론을 정리해서 설명해주기도 합니다.
표지를 첨부합니다. 한번 살펴보세요. 약간 강하게 헤드카피를 적어보았습니다." 참, 올 겨울 방학때 대학생이라면 한번 이 책에 도전해보는 것도 좋을 것 같습니다. 그리고 알고리즘 시험을 치르는 IT 기업의 취업 준비에도 도움이 될 수 있습니다.
"최고의 알고리즘을 찾을 때까지 당신의 뇌를 뛰게 하라!!"
'출간예정도서' 카테고리의 다른 글
[출간완료!!] 빅 데이터 시대를 위한 NoSQL 핵심 가이드(12월) (0) | 2011.12.14 |
---|---|
[출간완료!!] 웹 디자이너를 위한 jQuery (8) | 2011.11.08 |
[출간완료!!] 거꾸로 배우는 소프트웨어 개발 (0) | 2011.08.10 |
[출간완료!!] 처음부터 다시 배우는 HTML5 + CSS3: 실전 웹 표준 사이트 제작까지 (0) | 2011.06.20 |
[출간완료!!] 프로그래머 그 다음 이야기 (2) | 2011.06.16 |