프로그래밍 콘테스트 챌린징 for GCJ, TopCoder, ACM/ICPC, KOI/IOI 지은이 Takuya Akiba, Yoichi Iwata, Mastoshi Kitagawa 옮긴이 박건태, 김승엽 1판 1쇄 발행일 201 1년 10월 24일 펴낸이 장미경 펴낸곳 로드북 편집 임성춘 디자인 이호용(표지), 박진희(본문) 주소 서울시 관악구 신림동 1451-15 101호 출판 등록 제 2011-21호(2011년 3월 22일) 전화 02)874-7883 팩스 02)843-6901 정가 25,000원 ISBN 978-89-966598-4-6 93560 Programming Contest Challenge Book by Takuya Akiba, Yoichi Iwata, Mastoshi Kitagawa Copyright c2010 Takuya Akiba, Yoichi Iwata, Mastoshi Kitagawa All rights reserved. Original Japanese edition published by Mainichi Communications Inc. This Korean edition is published by arrangement with Mainichi Communications Inc., Tokyo in care of Tuttle-Mori Agency, Inc., Tokyo through EntersKorea Co., Ltd., Seoul 책 내용에 대한 의견이나 문의는 출판사 이메일이나 블로그로 연락해 주십시오. 잘못 만들어진 책은 서점에서 교환해 드립니다. 이메일 chief@roadbook.co.kr 블로그 www.roadbook.co.kr Q & A roadbook.zerois.net/qna
지은이 머리말 오늘날 Google Code Jam, TopCoder, ACM/ICPC 등 세계적인 프로그래밍 콘테스트가 개최되고 있습니다. 이 책은 프로그래밍 문제를 정확하게 그리고 가능한 많이 해결하 기 를 겨루는 프로그래밍 콘테스트를 다루고 있습니다. 프로그래밍 콘테스트는 누구나 가벼운 마음으로 참가할 수 있습니다. 예를 들어 Google Code Jam이나 TopCoder 같은 대회는 인터넷으로 콘테스트를 진행하기 때문에 인터넷으로 등록을 마친 후 정해진 시 간에 자신의 컴퓨터 앞에 앉아서 참가하는 것이 가능합니다. 프로그래밍 콘테스트는 세계적으로 유능하고 경험이 많은 프로그래머라 하더라도 좋은 성적을 내는 것이 그리 쉽지만은 않습니다. 이런 프로그래밍 대회에서 이기려면 유연한 발상과 폭넓은 지식을 이용하여 문제에 관한 알고리즘을 생각해야 하는 것은 물론이거 니와 코딩과 디버깅 과정도 거쳐야 합니다. 그렇지만 프로그래밍 콘테스트가 상급자만을 위한 무대는 아닙니다. 초보자도 풀 수 있 는 문제도 준비되어 있어 많은 참가자가 즐길 수 있도록 배려하고 있습니다. 또한 좋은 성적을 내지 못하더라도 능력을 향상시켜 자기계발이 되고, 즐겁고 유익한 시간을 보낼 수도 있을 것입니다. 이 책은 저자들이 다양한 프로그래밍 콘테스트에 참가한 경험 및 연습과 공부를 통해 얻은 지식과 노하우를 모아 집필한 것입니다. 주로 알고리즘과 사고하는 법에 관해 다 루고 있으며 매우 기초적인 내용부터 꽤 높은 수준의 토픽까지 아우르고 있습니다. 본 서는 각 토픽들을 난이도 및 의존 관계를 고려하여 구성하였으며, 토픽마다 설명과 예 제로 구성하였습니다. 이 책을 읽어 나가기 위한 전제 조건은 기초적인 프로그래밍 능력뿐입니다. 소스코드는 C++로 기술되어 있습니다만, 기본적인 기능만을 사용하고 있으므로 C++의 경험이 없 다 하더라도 읽는 데 큰 지장이 없도록 구성되어 있습니다. 저자들은 프로그래밍 콘테스트에 참가하기 시작했을 무렵부터 이런 책이 있으면 좋겠다 라는 생각을 해왔습니다. 부디 많은 분이 이 책을 활용해 프로그래밍 콘테스트를 즐기게 되길 기대합니다. 또 이후 프로그래밍 콘테스트가 한층 더 활발해졌으면 좋겠습니다. Takuya Akiba, Yoichi Iwata, Mastoshi Kitagawa
옮긴이 머리말 이 책은 프로그래밍 콘테스트에 대해 다루고 있습니다. 현재 다양한 프로그래밍 콘테스 트가 존재하며 세계의 많은 프로그래머들이 관심을 가지고 참여하고 있습니다. 책의 대 상 독자는 프로그래밍에 관심이 있는 학생에서부터 현업 프로그래머 그리고 프로그래밍 을 취미로 하고 있는 모든 사람을 아우르고 있습니다. 프로그래밍 콘테스트의 문제는 (개발자라면! 누구에게나) 흥미를 유발하게 하는 재미있는 문 제들로 구성되어 있습니다. 이 문제들을 풀기 위해서는 기초적인 알고리즘을 기반으로 독특한 발상의 전환이 필요합니다. 책 전반에 걸쳐 수년간 프로그래밍 콘테스트에 도전 한 저자들의 문제 해결을 위한 놀라운 접근 방법을 볼 수 있을 것입니다. 우선 문제를 읽고 혼자 또는 옆의 동료와 함께 고민하여 해결책을 찾고 프로그래밍을 한다면 더욱 즐겁게 이 책을 읽어 나갈 수 있으리라 생각합니다. 처음에는 그다지 좋아 보이지 않는 해결책이라도 또다시 고민의 고민을 거듭하다 보면 놀라우리만큼 간단한 솔루션을 찾을 수도 있을 것입니다. 그런 다음 저자들의 해결책과 비교해보고, 더 좋은 해결책을 찾는 고민을 해보기를 바랍니다. 학생에게 대한민국 미래산업의 주역이 될 소프트웨어 개발에 관심을 가지고 있는 학생 여러분! 기성 소프트웨어 개발자들이 여러분에게 바라는 것은 커다란 시스템의 요구사항을 분석 정리하고 설계 개발하는 것이 아닌, 놀라운 상상력! 재미있고 재치 있는 발상으로 남다 른 문제 해결 경험(그것이 프로그래밍과는 관계 없다 할지라도)일 것입니다. 표준학습으로 트레이닝된 두뇌의 결과가 아닌 나만의 기발하고 엉뚱한 상상이 모여 풀 기 어려운 난해한 알고리즘 문제들을 너무나도 우스우리만큼 간단히 해결하는 마법의 지팡이가 될 수도 있다고 생각해 본적은 없는지요?
처음에는 낯설고 어려워 보이는 문제라고 하더라도 해결책을 찾기 위해 상상하고 고민 하여 답을 얻고, 거기서 즐거운 요령을 배우고 익숙해지면 더욱 새로운 것을 창조해 온 우리의 삶처럼 소프트웨어 분야에서도 아직 개척하지 못한 수많은 문제들이 여러분의 마법의 지팡이를 기다리고 있습니다. 부디 여러분만의 즐거운 상상으로 재미있게 이 책을 할용하기를 바랍니다. 개발자에게 요즘은 개발자의 생산성에 기여하는 프레임워크가 워낙 발달되어 있어 개발자는 비즈니 스 플로우만 잘 이해하면 개발자간의 실력 차이를 거의 느낄 수 없을 정도의 프로그래 밍이 가능한 환경입니다. 하지만 잘 구조화된 프레임워크상에서 수십만 라인을 코딩하 며 프로그래밍에 대해 회의감을 느끼지는 않았는지요? 처음 프로그래밍을 접했을 때의 답을 얻기 위해 들였던 시간과 고민들 그리고 마침내 해결했을 때의 희열을 그리워하고 있지는 않는지요? 이 책은 현업 프로그래머라고 할지라도 또는 알고리즘에는 자신 있다고 하는 프로그래 머도 쉽게 풀기 어려운 문제들을 제시하고 있습니다. 물론 책에서 나오는 문제는 바로 해결 가능한 문제도 있는가 하면, 커피를 한 잔 마시며 오랜 시간 고민해야 하는 문제도 있으리라 짐작됩니다. 그런 문제들은 시간을 내서 동 료들과 함께 회의하고 풀어보는 시간을 갖기를 추천합니다. 그리고 처음 프로그래밍을 접했을 때의 설렘을 이 책을 통해 다시 느끼게 되기를 바랍니다. 특히 프로그래밍은 단지 코드를 서술하는 것이 아니라 알고리즘과 함께 쓰는 예술적 표 현이라는 것을 다시 한번 마음 깊이 느끼는 계기가 되었으면 합니다. 부디 즐겁게 이 책을 읽어 나가길 바랍니다. 박건태, 김승엽
목차 지은이 머리말... 3 옮긴이 머리말... 4 CHAPTER 1 프로그래밍 콘테스트 (초급편) 1-1 프로그래밍 콘테스트란 무엇인가요?... 12 1-2 어떤 콘테스트가 있나요?... 15 세계적인 규모의 콘테스트 - Google Code Jam(GCJ)... 15 상위 랭크를 목표로! - TopCoder... 15 역사 깊은 콘테스트 - ACM/ICPC... 16 중학생, 고등학생을 위한 정보 올림피아드 - KOI/IOI... 16 웹에서 자동 채점 - online judge... 16 1-3 이 책은?... 17 다루는 내용... 17 사용하는 언어... 17 문제를 다루는 방법... 17 프로그램은... 18 이 책을 다 읽은 후... 18 1-4 어떻게 해답을 제출하나요?... 19 POJ에 제출하는 방법... 19 GCJ에 제출하는 방법... 21 1-5 효율적인 알고리즘을 목표로!... 25 계산량이란?... 25 실행시간이란?... 25 1-6 가볍게 워밍업... 27 먼저 간단한 문제부터... 27 POJ 문제 [Ants]... 30 허들이 높아진 [제비 뽑기]... 33
CHAPTER 2 기초부터 시작하기 (초급편) 全 2-1 모든 것의 기본 전 탐색... 40 재귀함수... 40 스택... 42 큐... 43 깊이 우선 탐색... 45 너비 우선 탐색... 49 특수한 상태의 열거... 53 가지치기... 55 2-2 탐욕 알고리즘... 57 코인 문제... 57 구간 스케줄링 문제... 59 COLUMN 알고리즘의 증명... 61 Best Cow Line... 62 Saruman s Army... 64 Fence Repair... 66 COLUMN 하프만 부호... 70 2-3 값을 기억해서 재활용하는 동적 설계법... 71 탐색의 메모화 및 동적 설계법... 71 COLUMN memset... 74 COLUMN 초기화... 76 COLUMN 다양한 DP... 76 점화식 공부... 80 COLUMN 재활용 방법... 83 COLUMN lower_bound... 91 계산 문제에 관한 DP... 91 2-4 데이터를 효율적으로 기억하는 데이터 구조... 96 트리 이진트리... 96 우선순위 큐와 힙... 97 이진탐색 트리... 105 Union-Find 트리... 113
2-5 모든 것이 사실은 그래프... 121 그래프란?... 121 그래프의 표현... 125 그래프 탐색... 129 최단경로 문제... 131 연습문제... 143 2-6 GCJ 문제에 도전하기(1)... 150 Minimum Scalar Product... 150 Crazy Rows... 152 Bribe the Prisoners... 155 Millionaire... 158 CHAPTER 3 여기서 차이가 난다 (중급편) 3-1 수학적인 문제를 푸는 요령... 164 유클리드 호제법... 164 COLUMN 증명이나 법칙... 168 소수에 관한 기본적인 알고리즘... 168 나머지 계산... 173 제곱승을 고속으로 계산한다... 174 3-2 값 탐색만이 아니다 이진탐색... 178 정렬된 열로부터 값 찾기... 178 해를 가정하고 가능할지 판정... 180 COLUMN 종료 조건... 182 최소 값의 최대화... 182 평균최대화... 184 3-3 엄선 자주 출제되는 유형 테크닉(1)... 187 inchworm 알고리즘... 187 반전... 192 COLUMN 집합 정수 표현... 199
탄성충돌... 202 half 전열거... 205 표준압축... 209 3-4 여러 가지 데이터 구조를 조작해보자... 213 세그먼트 트리... 213 COLUMN Sparse 테이블... 221 BIT란?... 221 버킷 방식과 평방 분할... 232 3-5 동적 계획법을 연구한다!... 241 비트 DP... 241 COLUMN 완벽매칭의 갯수... 251 행렬 거듭제곱... 251 COLUMN 좀 더 고속으로 점화식 계산하기... 254 데이터 구조를 이용한 고속화... 260 3-6 네트워크 플로우... 263 최대흐름... 263 최소절단... 268 COLUMN 여러 가지 그래프에 대한 최대흐름... 269 COLUMN 고속의 플로우 알고리즘... 272 이분매칭... 274 일반매칭... 277 매칭 변 덮개 안정집합 점 덮개... 278 최소비용흐름... 280 COLUMN 여러 가지 그래프에 대한 최소비용흐름... 287 연습문제... 289 3-7 GCJ 문제에 도전해보자(2)... 315 Numbers... 315 No Cheating... 317 Stock Charts... 319 Watering Plants... 322 COLUMN 계산 오차... 327 Number Sets... 328 Wi-fi Towers... 330
CHAPTER 4 좀 더 연구하자! (상급편) 4-1 복잡한 수학적 문제... 336 행렬... 336 mod의 세계... 342 열거... 348 대칭성이 있는 열거... 354 4-2 게임의 필승법을 생각하자!... 360 게임과 필승법... 360 Nim... 367 Grundy 수... 374 4-3 그래프 마스터의 길... 380 강한 연결 성분 분해... 380 2-SAT... 385 LCA... 389 4-4 엄선! 자주 출제되는 테크닉(2)... 399 스택의 사용... 399 데큐의 이용... 402 LogStepDP... 412 4-5 GCJ 문제에 도전해봅시다(3)... 418 Mine Layer... 418 Year of More Code Jam... 424 COLUMN 다배장 연산... 428 Football Team... 428 Endless Knight... 434 The Year of Code Jam... 438 찾아보기... 444
CHAPTER 1 프로그래밍 콘테스트 초급편
1-1 프로그래밍 콘테스트란 무엇인가요? 이번 절에서는 프로그래밍 콘테스트에 대해 전반적인 설명을 합니다. 프로그래밍 콘테스트란 이름 그대로 프로그래밍을 겨루는 대회입니다. 문제 해결을 겨 루는 콘테스트, 성능을 겨루는 콘테스트, 아이디어를 겨루는 콘테스트 등 다양한 프로 그래밍 콘테스트가 있습니다. 이 책에서는 그 중에서도 문제 해결을 겨루는 콘테스트를 다룹니다. 문제 해결을 겨루는 콘테스트는 시작과 함께 몇 개의 문제가 제시되며, 가능한 많이 해 결하는 것을 목표로 합니다. 그럼 문제는 어떤 형태를 띠고 있을까요? 제비 뽑기 어느 날 친구가 봉지를 들고 와 당신에게 게임을 제안했습니다. 봉지에는 숫자가 쓰여 있는 n장의 종 이가 들어 있습니다. 당신은 봉지에서 종이를 한 장 뽑고, 숫자를 확인한 후 다시 봉지에 넣는 동작을 4번 반복하여, 그 숫자의 합이 m이면 당신의 승리, 그렇지 않으면 친구가 승리하게 됩니다. 당신은 이 게임을 몇 번이나 해 보았지만 한번도 이기지 못했습니다. 화가 난 당신은 봉지를 찢어 모든 종이를 꺼 낸 후 정말 이길 수 없었는지 조사를 했습니다. 종이에 쓰여 있는 숫자가 K 1, K 2..., K n 일 경우, 합이 m 이 되는 경우가 있는 지를 조사하고, 방법이 있다면 Yes, 없다면 No를 출력하는 프로그래밍을 작성하 세요. 제약 1 n 50 1 m 10 8 1 k i 10 8 예1) 입력 n = 3 m = 10 k = {1, 3, 5 12 CHAPTER 1
출력 1 Yes(예를 들어 1, 1, 3, 5가 나오면 합이 10이 됩니다) 예2) 입력 n = 3 m = 9 k = {1, 3, 5 출력 No(합이 9가 되는 경우가 존재하지 않습니다.) 이 문제를 풀기 위해 다음과 같이 프로그래밍합니다. #include <cstdio> const int MAX_N = 50; int main() { int n, m, k[max_n]; // 표준 입력 scanf("%d %d", &n, &m); for(int i = 0; i < n; i++){ scanf("%d", &k[i]); // 합이 m이 되는 조합이 있는지를 나타내는 플래그 bool f = false; // 4중 루프로 n장만큼 돌리면서 모든 방법을 조사함 for (int a = 0; a < n; a++){ for (int b = 0; b < n; b++){ for(int c = 0; c < n; c++){ 1 출력의 () 안의 문자열은 설명을 돕기 위한 것으로 프로그래밍에서는 출력하지 않습니다. - 옮긴이 프로그래밍 콘테스트 13
for(int d = 0; d < n; d++){ if(k[a] + k[b] + k[c] + k[d] == m){ f = true; if (f) puts("yes"); else puts("no"); return 0; 콘테스트 중에 소스코드를 제출하면 자동으로 컴파일되고 실행되어, 판정을 위해 준비 된 입력 파일이 입력됩니다. 그리고 출력 확인 후 결과가 나옵니다. 여기서 중요한 것은 프로그램 실행에는 제한시간이 있다는 점입니다. 대부분의 콘테스 트에서, 실행에 할애하는 시간의 제한은 단 몇 초입니다. 프로그램 실행이 정해진 시간 을 초과하면 종료되어 오답 처리됩니다. 그렇기 때문에 효율적인 해결책을 생각해 내야 만 합니다. 예를 들어 이 문제에서는 [1 n 50]라는 조건이 있습니다. 이는 위와 같이 단순히 4중 루프로 프로그래밍했다 하더라도 실행 시간은 1초도 걸리지 않습니다. 만약 조건이 [1 n 1000]이라면 어떻게 될까요? 4중 루프를 돌리는 프로그램을 만들 어서는 시간 제한에 걸려 오답 처리가 되어 버릴 것입니다. 하지만 조건 [1 n 1000]의 경우라도 시간 제한에 걸리지 않고 해결할 수 있는 효율적 인 알고리즘이 존재합니다(이후 다시 다루도록 하겠습니다). 정리해보면 프로그래밍 콘테스트는 다음과 같은 기본기가 필요합니다. 효율적인 알고리즘을 생각하여 정확하게 구현할 수 있는 능력 문제 접근에 대한 유연한 발상 및 기초적인 알고리즘 지식 14 CHAPTER 1
1-2 어떤 콘테스트가 있나요? 다양한 콘테스트 중에서 몇 가지 유명한 콘테스트를 소개합니다. 세계적인 규모의 콘테스트 - Google Code Jam(GCJ) Google이 매년 개최하고 있는 세계 규모의 프로그래밍 콘테스트입니다. 2~3시간 안에 4문제 정도를 해결해야 하는 형식으로 진행됩니다. 온라인에서 이루어지는 예선을 통과 하면 현장에서 개최되는 결승전에 참가할 수 있습니다. 이 콘테스트의 특징은 문제마다 Small과 Large라는 2개의 입력 데이터가 준비되어 있다는 것입니다. 입력 사이즈에 따 라 어려운 문제라도 간단히 해결할 수 있는 경우도 있으며, 폭 넓은 레벨의 참가자가 즐 길 수 있는 콘테스트입니다. 또한 GCJ에서는 서버에서 자동으로 실행하는 게 아니라 자 신의 로컬에서 실행한 후 결과를 함께 제출하는 형식의 콘테스트입니다. 상위 랭크를 목표로! - TopCoder TopCoder는 프로그래밍 콘테스트를 기획하고 개최하는 회사로서 다양한 장르의 콘테 스트를 개최하고 있습니다. 그 중 하나인 알고리즘 파트에서는 거의 매주 SRMSingle Round Match이라고 하는 형식의 콘테스트가 열리고 있습니다. 이 콘테스트는 다음과 같 은 특징이 있습니다. 1. 짧은 시간(1시간 15분) 안에 문제 3개 풀기 2. 종료할 때까지 결과는 알 수 없으며, 약간의 미스라도 있으면 0점 처리 3. 코딩 시간 종료 후 다른 참가자의 프로그램을 읽고 버그를 찾아 잘못된 답이 리턴 되도록 하여 스코어를 획득하는 격추 라운드가 존재함 특히 3번의 특징은 이 콘테스트만이 가지는 유일한 특징으로 다른 사람의 프로그램을 읽을 수 있는 좋은 기회입니다. SRM에서의 결과를 바탕으로 참가자의 순위를 매기는 Rating(등급 평가) 시스템이 있어 인기가 매우 좋습니다. 또한 연 1회 TCOTopCoder Open 라는 토너먼트 대회가 개최되며, 이는 온라인 예선을 통과하면 라스베이거스에서 열리 는 결승전에 참가할 수 있는 자격이 주어집니다. 프로그래밍 콘테스트 15
역사 깊은 콘테스트 - ACM/ICPC ACM/ICPC는 미국의 ACMAssociation for Computing Machinery이 주최하는 대학생을 위한 콘테스트로, 가장 역사가 깊은 프로그래밍 콘테스트입니다. 3인 1조의 팀을 이루어 5시 간 안에 10문제 정도를 푸는 형식으로 진행됩니다. 3인이 한 대의 PC를 사용하며, 다른 콘테스트에 비해 문제 수가 많고 어려운 문제가 많아 팀 워크가 무엇보다 중요합니다. 한국에서는 국내 예선을 통과해야 아시아 대회에 참가할 수 있습니다. 아시아 대회에서 좋은 성적을 내면 세계 대회에 나갈 수 있습니다. 중학생, 고등학생을 위한 정보 올림피아드 - KOI/IOI 정보 올림피아드는 과학 올림피아드의 일종으로 중학생, 고등학생을 대상으로 한 프로그 래밍 콘테스트입니다. 한국 정보 올림피아드에 참가하여 좋은 성적을 내면 국제 정보 올 림피아드에 한국 대표로서 참가할 수 있습니다. 다른 콘테스트에서는 많은 문제를 빨리 해결하는 것을 목표로 합니다만, 정보 올림피아드에서는 제한된 시간 안에 문제만 해결 하면 시간은 관계 없으며 다른 콘테스트에 비해 1문제를 풀 수 있는 시간이 훨씬 깁니다. 중, 고생을 위한 콘테스트라고 하지만 매우 난이도 높은 문제가 출제되고 있습니다. 웹에서 자동 채점 - online judge Web에는 과거 프로그래밍 콘테스트 문제를 자동 채점해주는 online judge라는 시스템 이 있습니다. 이 시스템을 이용해서 연습할 수 있습니다. 또한 그 중에는 정기적으로 콘 테스트를 개최하는 곳도 있으므로 참가해보는 것도 좋을 것입니다. 그 중에서 유명한 online judge 사이트를 몇 가지 소개합니다. http://acm.pku.edu.cn/judgeonline 많은 문제가 있습니다. http://judge.u-aizu.ac.jp/onlinejudge/ 영어 또는 일본어로 되어 있습니다. http://www.spoj.pl/ 다양한 언어를 사용할 수 있습니다. http://acm.sgu.ru/ 지난 콘테스트의 참가 및 가상 콘테스트 등을 제공합니다. 16 CHAPTER 1
1-3 이 책은? 이 책에서 다루는 내용과 주의점에 대해 설명 2 합니다. 다루는 내용 이 책에서는 주로 프로그래밍 콘테스트에서 자주 출제되는 전형적인 문제나 기초적인 알고리즘의 해설, 알아 두면 도움이 될 만한 테크닉을 설명합니다. 문제의 해결책이나 기초적인 알고리즘을 단지 외우는 것만으로는 어려운 응용 문제, 즉 유연한 발상이 필 요한 문제를 풀기에는 한계가 있습니다. 따라서 POJ의 과거 기출 문제나 실전 문제를 더욱 깊이 있는 학습 방법을 제공합니다. 사용하는 언어 콘테스트마다 사용 가능한 언어는 다릅니다만, 이 책에서는 거의 모든 콘테스트에서 사 용 가능하며 실행 속도가 빠르고 라이브러리가 충실한 C++을 이용합니다. 또한 기본적 으로 소스코드는 g++용으로 구현되어 있습니다. 문제를 다루는 방법 예상했겠지만 세계적인 규모의 대회는 문제가 영어로 되어 있습니다. 문제에서 사용되 는 영문은 그다지 어렵지 않고 사용되는 단어 역시 매우 한정되어 있어, 금방 익숙해질 것입니다. 물론 영어 시험이 아니므로 자유롭게 사전을 사용하는 것도 가능합니다. 영 어 독해에 관해서는 이 책의 범위를 넘어서므로 이 책에서는 앞의 예시와 같이 한국어 로 요약한 형식으로 문제를 다루도록 하겠습니다. 2 책에 나오는 예제들은 여러분이 더 쉽게 이해하고 해결할 수 있도록 간단하고 쉬운 형태로 문제를 변형하였습니다. 실제 영문 으로 된 문제는 웹에서 검색하면 영문 문제를 볼 수 있습니다. 프로그래밍 콘테스트 17
프로그램은 다수의 콘테스트에서 입력은 지정된 형식에 따라 표준 입력을 이용하지만, 이 부분도 책의 범위를 벗어나므로 모든 입력은 main 함수에서 읽어 들였다는 가정하에 글로벌 변 수에 넣어 두고 함수 solve가 호출되는 형식으로 문제를 풀도록 하겠습니다. 일단 앞서 나온 예제를 살펴봅시다. // 입력은 이곳에 읽어 들였다고 가정 int n, m, k[max_n]; void solve() { bool f = false; for (int a = 0; a < n; a++){ for (int b = 0; b < n; b++){ for(int c = 0; c < n; c++){ for(int d = 0; d < n; d++){ if(k[a] + k[b] + k[c] + k[d] == m){ f = true; if (f) puts("yes"); else puts("no"); 이 책을 다 읽은 후 이 책을 다 읽고 연습을 더 하고 싶다면 웹을 통해 관련 문제를 풀어 보거나 TopCoder 의 Practice Room이라는 시스템을 이용하면 좋을 듯합니다. 특히 TopCoder에서는 해설 Editorial이 있기도 하고, 다른 사람의 솔루션을 읽을 수 있어, 혼자서 해결하지 못한 문제 도 해결하는 데 도움이 많이 됩니다. 18 CHAPTER 1
1-4 어떻게 해답을 제출하나요? 이번에는 POJ와 GCJ에서 해답을 제출하는 방법을 소개합니다. POJ에 제출하는 방법 실제 POJ에 프로그래밍한 코드를 제출해봅시다(http://acm.pku.edu.cn/Judge Online 참고). 우선 POJ를 이용하기 위해서 등록합니다. 등록 화면에는 이름과 패스워드 외에도 E-mail 등을 입력하는 폼이 있습니다만 필수 항목은 아닙니다. 등록 화면 등록을 마쳤다면 테스트용 문제 A+B Problem을 제출해봅시다. 문제 화면 프로그래밍 콘테스트 19
A+B Problem 문제는 표준 입력으로부터 정수 a, b를 읽어 들여 a+b의 합을 표준 출력 으로 출력합니다(A+B Problem에는 제출하는 예에 관해서도 설명되어 있으므로 참고하 세요). 다음의 프로그램을 제출해봅시다. 문제를 입력한 후 페이지의 하단에 Submit을 클릭하면 프로그램이 제출됩니다. 결과는 다음과 같습니다. Accepted 무사히 Accepted가 되었습니다. 정답의 경우에는 Accepted가, 만약 잘못된 답을 제출 하는 경우에는 Wrong Answer 또는 Compile Error 등의 결과가 나옵니다. printf( %d\n, a+b);를 printf( %d\n, a*b);로 변경한 후 다시 제출해볼까요? 우리의 예상대로 Wrong Answer가 결과 화면에 표시됩니다. 20 CHAPTER 1
Wrong Answer 위의 Problem은 런타임 시간 제약을 나타냅니다. A+B Problem의 경우에는 1000MS입 니다. 제약된 시간을 초과하는 프로그램을 제출하면 Time Limit Exceeded라는 결과가 나옵니다. 예를 들어 printf 다음 행에 for(;;)을 추가하고 제출해봅시다. Output Limit Exceeded 시스템 사용 방법은 대체로 이런 느낌입니다. Submit의 결과에는 다음과 같은 종류가 있습니다. Runtime Error Memory Limit Exceeded Presentation Error Output Limit Exceeded Compile Error System Error, Validator Error 메모리 엑세스 위반이나 예외 등의 경우 프로그램이 사용 가능한 메모리 제약을 초과한 경우 정답임에도 개행이나 공백 등의 출력 형식이 잘못된 경우 출력 위반의 경우 컴파일 에러인 소스코드를 제출한 경우, 컴파일 에러는 Online Status의 [Compile Error]를 클릭하면 관련 정보를 볼 수 있습니다. 시스템 측에서 에러가 원인으로 프로그램의 정답, 오답의 판정을 할 수 없는 경우 GCJ에 제출하는 방법 이번에는 GCJ 시스템 제출 방법에 관해 알아보겠습니다(http://code.google.com/ codejam/ 참고). 홈페이지에는 콘테스트에 관한 일정 및 룰 등 다양한 정보가 게재되어 있으므로 참고 하기 바랍니다. 프로그래밍 콘테스트 21
GCJ 홈페이지 Practice라는 버튼을 누르면 과거 콘테스트 문제 일람 등을 볼 수 있습니다. 과거 콘테스트 일람 등 GCJ는 등록하지 않아도 연습하는 것이 가능합니다만, 참가할 때 등록할 필요가 있으므 로 사전에 등록해 두는 것이 좋을 것입니다. 22 CHAPTER 1
Past Contests의 콘테스트 링크를 클릭하면 연습용 페이지로 이동합니다. Top Scores 및 Full Scoreboard 등을 클릭하면 결과를 참조할 수 있습니다. Full scoreboard에서 는 상세한 스코어뿐만이 아니라 제출된 소스코드를 다운로드하는 것도 가능합니다. Submissions에서는 문제마다의 제출 현황 및 배점이 표시됩니다. 위에서부터 제출용 폼, 문제, 입력 사양, 출력 사양, 제약, 샘플 순으로 나열되어 있습니 다. 제약에 Small과 Large가 있습니다. 이것을 제외하면 POJ와 거의 유사합니다. Download A-small.in이라고 쓰여있는 링크를 클릭하면 입력 파일을 다운로드할 수 있 습니다. 실전에서는 입력 파일을 다운로드하면 카운트다운이 시작되고, 시간 제약을 초 과하면 Time Limit이 되어 Incorrect와 같은 취급을 받습니다. 입력 파일을 다운로드했 다면 자신이 만든 프로그램에 전달해 결과 파일을 출력합니다. Submit 버튼을 누르면 제출용 폼이 나타납니다. Your output file에 출력한 결과 파일을, source file(s)에 소스 코드를 지정*해서 Submit file 버튼을 누릅니다. 연습의 경우 결과가 바로 표시됩니다. (다음 장 참고) *소스 코드 지정은 실전의 경우에만 해당함 실전에서는 Small에 제출하면 바로 Correct인지 Incorrect인지가 표시됩니다. Incorrect 의 경우에는 몇 번이라도 다시 제출하는 것이 가능합니다.* Large의 경우에는 콘테스트 가 끝날 때까지 결과를 알 수 없습니다. 제출 제약 시간 안에 몇 번이라도 다시 제출할 수 있습니다만 시간을 초과하면 다시는 제출할 수 없게 되므로 신중하게 제출해야 합 니다. * Incorrect의 경우 페널티가 주어집니다. 프로그래밍 콘테스트 23
Submit 버튼을 누른 상태 콘테스트에서 최종적으로 득점의 합계가 큰 순으로 순위가 매겨집니다. Small을 푼 후 에 무리해서 Large를 해결할 필요는 없습니다. Large가 풀기 어려울 경우에는 다른 사 람이 해결한 문제나 바로 풀 수 있을 만한 Small 등을 우선적으로 푸는 것도 좋은 전략 이 되겠습니다. 해마다 또는 Round마다 룰이 변할 가능성이 있으므로 자세한 정보는 GCJ 홈페이지를 확인하도록 합시다. 24 CHAPTER 1
1-5 효율적인 알고리즘을 목표로! 효율적인 알고리즘을 위한 사고에서 중요한 계산량을 소개합니다. 계산량이란? 문제에 맞춰 효율적인 알고리즘을 생각할 때 중요한 것은 계산량입니다. 생각해낸 알고 리즘 전부를 코딩하고 테스트를 한다는 것은 있을 수 없겠지요. 알고리즘이 충분히 효 율적인지 판단하기 위해 알고리즘 계산량을 측정해야만 합니다. 통상 무엇에 비례할까 로 생각할 수 있는 계산량을 알고리즘의 Order라고 합니다. 예를 들 어 12페이지의 프로그램에서는 4중 루프가 n번 돌기 때문에 실행시간은 n 4 에 비례합니다. 그리고 n 4 에 비례하는 것을 O(n 4 )라고 쓰고, 이 실행 시간을 [O(n 4 )시간]*이라고 씁니다. *이것을 런다우 기법(Landau notation) 또는 기호로서 O를 이용하여 (런다우의)O-기법이라고 합니다. 정확한 의미는 비례한다 라고 할 수는 없지만 지금은 우선 그렇게 인식하는 것으로 충분합니다. O(n 4 )라고 쓰는 것만으로 n 4 에 비례하는 실행시간이다 라는 표현을 나타냅니다. 실행시간이란? 프로그램 실행시간은 계산량만으로 결정되는 것은 아닙니다. 예를 들어 루프 안에서 처 리의 복잡함에 의해 실행 시간은 변하기도 합니다. 어떤 경우는 수 십 배의 차이가 나는 경우도 있습니다. 또한 단순히 알고리즘에 따른 계산량 만으로도 프로그램 속도의 차이 는 큽니다. 예를 들어 n=1000의 경우 O(n 3 )시간 알고리즘과 O(n 2 )시간 알고리즘의 실 행 시간은 단순히 생각해도 1000배 정도입니다. 즉 프로그램 실행시간을 짧게 하기 위 해서는 우선 알고리즘 계산량이 중요하다는 뜻입니다. 프로그래밍 콘테스트 25
알고리즘이 제한시간 안에 실행 가능한지 판단하기 위해서는 계산량 오더 식에 최대치 를 대입해볼 필요가 있습니다. 예를 들어 O(n 2 )시간 알고리즘을 생각하고 있고 문제가 (n 1000)이라는 제약일 경우 n 2 에 n=1000을 대입하면 1,000,000이 됩니다. 이 값을 바탕으로 다음과 같이 짐작할 수 있습니다. 실행시간 제한이 1초인 경우 1,000,000 여유가 있음 10,000,000 적어도 제한시간 안에는 결과가 나옴 100,000,000 매우 심플한 처리가 아닌 경우에는 위험 26 CHAPTER 1
1-6 가볍게 워밍업 이번에는 프로그래밍 콘테스트 문제 및 그 문제에 관한 알고리즘을 생각하고, 계산량을 측정하는 등에 관한 일련의 과정에 익숙해지는 것을 목표로 몇 가지 문제를 다루어 보겠습니다. 어려운 문제도 포함되어 있으니 모 두 해결하지 못해도 괜찮습니다. 해설을 읽고 재미를 맛보는 것으로 충분합니다. 먼저 간단한 문제부터 삼각형 n개의 봉이 있습니다. 봉 i의 길이는 a i 입니다. 여러분은 3개의 봉을 선택해서 가능한 둘레의 길이가 긴 삼각형을 만들려고 합니다. 둘레의 길이의 최대 값을 구하세요(만약 삼각형을 만들 수 없는 경우에는 0을 답합니다). 5개의 봉으로 삼각형을 만드는 예 제약 3 n 100 1 a i 10 6 프로그래밍 콘테스트 27
예1) 입력 n = 5 a = {2, 3, 4, 5, 10 출력 12(3, 4, 5를 선택했을 경우) 예2) 입력 n = 4 a = {4, 5, 10, 20 출력 0(어떠한 경우라도 삼각형을 만들 수 없음) 3개의 봉을 선택했을 경우, 그 3개의 봉으로 삼각형을 만들 수 있는 필요충분조건은 다 음과 같습니다. 가장 긴 봉의 길이 다른 2개의 봉 길이의 합 삼각형을 만드는 조건 28 CHAPTER 1
3중 루프(삼각형의 변의 수)로 선택할 수 있는 모든 봉을 조사하고, 위의 식을 이용해 삼각형을 만들 수 있는 지를 판단한 후, 만들 수 있다면 답의 후보가 된다. 바로 이런 알고리즘을 생각할 수 있습니다. 3중 루프를 이용하면 계산량은 O(n 3 )시간입니다. n 3 에 n=100을 대입하더라도 10 6 이므 로 이 계산식은 충분히 시간 제한 안에 해결이 가능합니다. *이 문제는 O(n log n)시간으로 보다 효과적으로 풀 수 있습니다. 흥미가 있다면 도전해보세요. int n, a[max_n]; void solve() { int ans = 0; //답 // 봉을 중복해서 선택하지 않도록 i < j < k가 되도록 하고 있다. for(int i = 0; i < n; i++){ for(int j= i+1; j < n; j++){ for(int k = j+1; k < n; k++){ int len = a[i] + a[j] + a[k]; // 둘레의 길이 int ma = max(a[i], max(a[j],a[k])); // 가장 긴 봉의 길이 int rest = len - ma; // 나머지 두 봉의 합 if(ma < rest){ // 삼각형을 만들 수 있으므로, 답을 갱신할 수 있으면 갱신 ans = max(ans, len); printf("%d\n", ans); 프로그래밍 콘테스트 29
POJ 문제 [Ants] Ants(POJ No.1852) 길이가 Lcm인 장대(horizontal pole) 위를 n마리의 개미가 초당 1cm의 속도로 걷고 있습니다. 개미는 장대의 끝에 도착하면 장대 밑으로 떨어집니다. 또한 장대 위는 매우 좁아서 교차할 수 없어 두 마리의 개미가 마주치면 반대 방향으로 돌아가야 합니다. 우리는 개미가 장대의 어디에 위치(Xi)하고 있는지를 알 수 있습니다만, 불행히도 어느 쪽으로 향해 걷고 있는지는 알 수 없습니다. 모든 개미가 장대로부터 떨어질 때까지 걸리는 최소시간과 최대시간을 각각 구하세요. 장대와 개미의 모습 제약 1 L 106 1 n 106 1 X i L 예 입력 L = 10 n = 3 x = {2, 6, 7 출력 min = 4 (좌, 우, 우) max = 8 (우, 우, 우) 30 CHAPTER 1