전공 필수과목인 자료구조와, 알고리즘을 학습한 학생이라면, 즉 컴퓨터 학부 학생으로서 멋진 경험을 얻을 수 있는 방법을 소개하고자 한다. 세계 곳곳의 타 대학 친구들과 교류 할 수 있고, 문제 해결 및 프로그래밍 능력 그리고, 팀워크를 발휘 할 수 있는 대회, ACM-ICPC (국제 대학생 프로그래밍 경시대회)이다.
본 기사는 2회에 걸쳐 ACM-ICPC대회 소개와, 대회 출제 문제 소개, 대회에 대한 교내 지원, 대회 준비법 그리고 대회를 통해 얻을 수 있는 이점 등을 소개한다.
1. ACM-ICPC 소개
컴퓨터 분야의 학회인 ACM(Association for Computing Machinery)이 주최하는 ACM-ICPC(International Collegiate Programming Contest)는 1970년 미국 Texas A&M 대학에서 열린 경시에 기원을 두고 있고, 당시 막 태동하는 컴퓨터분야의 학생들에게 도전 정신을 일깨워 주는 방법으로 미국과 캐나다에서 인기를 얻게 되었다. 이후 계속 발전하여 1977년 ACM 컴퓨터 학술대회에서 첫 경시가 열렸다. 1997년부터 IBM이 세계대회를 후원하면서 급속히 성장 하였으며, 2007년 기준 6,700팀(26800여명), 1,821개의 대학이 참가(매년 10-20%의 참가 인원 증가)한 세계에서 가장 규모가 큰 대학생 프로그래밍 경시대회이다.
팀은 한 명의 코치와 세 명의 경시자로 구성된다. 5시간의 경시 동안 8~10개의 문제가 주어지고, 세 명의 경시자로 구성된 한 팀당 한 대의 컴퓨터가 제공된다. 팀은 각 문제를 올바르게 해결하는 프로그램을 작성해야 한다.
문제를 해결하는 프로그램을 작성하면 이를 채점 받아야 하는데, 프로그램에 특정한 테스트 데이터를 넣어보고, 제한 시간 내에 작성된 답이 심사위원이 제시한 답과 비교 후 합격(Accept), 또는 불합격(Wrong Answer)을 판단하여 이를 팀에게 알려준다.
심사위원이 합격판단을 한 문제에 한하여 팀은 푼 문제의 개수가 올라가고, 문제 해결에 사용된 시간(경시 시작 시각부터 합격 판단을 받은 프로그램을 제출한 시각)과 벌점 시간(합격 판단을 받기까지 불합격 받은 제출횟수 * 20분)이 주어진다.
대회 종료 후 순위 결정은, 푼 문제의 수가 가장 많아야 하며, 푼 문제의 수가 동일할 경우 시간점수(경과시간 + 벌점시간)가 낮을 경우 높은 순위에 랭크된다.
대회는 각 지역 대회를 거쳐 세계결선(World Final)으로 치러진다. 각 지역 대회는 그 지역 대회 책임자의 책임 하에 지역대회 규칙 및 ICPC의 정책, 절차와 가이드라인에 따라 치러진다. 대회의 공식 언어는 영어이고 때문에 대회의 모든 인쇄물은 영어로 써진다. 현재 아시아 지역은 아래와 같은 지역에서 대회를 개최하고 있다.
● 인도, 콜카타
● 중국, 북경
● 일본, 아이주
● 한국, 서울
● 필리핀, 마닐라
● 대만, 카오슝
● 방글라데시, 다카
● 중국, 광저우
● 이란, 테헤란
● 인도, 봄베이
아시아에 있는 대학은 어느 아시아 지역대회라도 참가할 수 있으나, 경시자는 1년에 최대 두 개의 아시아 지역대회에만 참가할 수 있다. 지역대회의 지원팀수가 많을 경우 지역대회 예선을 실시하기도 한다. (서울 대회의 경우 매년 9월~10월에 온라인 지역예선이 개최된다.)
아시아 지역 대회 중 하나인 서울 대회에 대해 알아보면, 대회 진행은 2단계로 이뤄진다. 첫 단계는 보통 9월 하순에 치러지는 인터넷 예선인데, 국내 약 400여 개 팀(1200명) 중 70~80팀이 서울 대회에 진출 할 수 있다. 서울 대회는 11월 백범 김구기념관에서 이틀에 거쳐 진행된다.
서울대회의 특징은 ACM-ICPC대회뿐만 아니라, 대학생 프로그래밍 경시대회를 겸한다는 것이다. 대학생 프로그래밍 경시대회는 행정안정부가 주최하는 국내대회로써 해외지역에서 참가한 팀을 제외하고 순위를 정해 시상한다. 때문에 대회에서 좋은 성적을 얻을 경우 ACM-ICPC대회 뿐 아니라 대학생 프로그래밍 경시대회에 대한 상장을 따로 받을 수 있다.
(2009년 ACM-ICPC 서울 지역 대회 결과 - 숭실대학교는 8위, 9위, 12위, 14위를 했으며, 같이 진행된 대학생 프로그래밍경시대회에서는 5위를 차지했다.)
각 지역대회에서 1~2위를 한 팀은 세계대회 출전 자격을 얻는다. 지난 2010년 2월 1일부터 6일까지 중국 하얼빈에서 개최된 세계대회의 경우 중국 상하이교통대가 1위를 차지했으며, 국내 대학의 경우 서울대가 14위를 하였다. 90여개 국가 7000여개의 대학이 학교의 이름을 걸고 출전하는 대회인 만큼 대회는 패기와 열정이 넘친다.
2. 대회 문제 소개
문제해결 능력을 평가하는 대회이기 때문에 경시자의 Algorithm과 Data Structure의 지식을 필요로 한다. 많은 Algorithm이 존재하지만, 우선 대회에 자주 출제되는 유형의 Algorithm과 Data Structure는 아래와 같다.
● Sorting
● Search
● Stack(DFS), Queue(BFS)
● Tree, Heap, BIT(Binary indexed Tree)
● Graph, Network Flow
● MST(Minimum Spanning Tree), aov, aoe
● Greedy method
● Divide and conquer
● DP(Dynamic Programming)
● Flood Fill, Plane Sweeping
● Backtracking
● Pattern matching
● Computational Geometry
실제 대회에 출제되는 문제와 유사한 문제를 하나 다뤄 보고자 한다.
|
연속부분 최대곱
N(1 <= N <= 10,000)개의 양의 실수가 주어질 때 1개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아 그 곱을 출력하는 프로그램을 작성하시오.
입력
첫째 줄은 나열된 실수들의 개수 N이 주어지고, 그 다음 줄부터는 N개의 양의 실수가 한 줄에 하나씩 들어있다.
출력
계산된 최대값을 소수점이하 넷째 자리에서 반올림하여 출력한다. 제한 시간은 1초이다.
입·출력 예
|
Input (Standard Input) |
Output (Standard Output) |
|
8
1.1
0.7
1.3
0.9
1.4
0.8
0.7
1.4 |
1.638 |
출처 : KOI(한국 정보올림피아드) 문제
|
solution 1) Time Complex : O(N^3)
나열된 실수 N개에 대하여 시작지점에 대한 point, 끝 지점에 대한 point를 지정한 후 시작 지점부터 끝 지점까지 연산한다. 연산된 결과 값 중 가장 큰 값을 프로그램 결과 값으로 출력한다.
solution 2) Time complex : O(N^2)
미리 1번째부터 N번째까지의 곱을 구한 후 배열에 저장한다. 이후 나열된 실수 N개에 대하여 시작지점에 대한 point, 끝 지점에 대한 point를 지정 한 후 (1 ~ 끝점까지의 곱)/(1 ~ 시작점까지의 곱)의 값 중 가장 큰 값을 프로그램 결과 값을 출력한다.
solution 1)과 비교하여 연산에 대한 시간복잡도가 n에서 1로 줄어 더 효율적인 프로그램이라 볼 수 있다.
solution 3) Time complex : O(N)
data[i]를 주어지는 수열에서 i번째 원소라고 할 때, 부분문제 d[i]를 다음과 같이 정의할 수 있다.
table[i] : 1~i에서, data[i]를 마지막 원소로 하는 연속부분 최대 곱
data[i]가 마지막 원소가 되어야 하기 때문에, 다음과 같은 두 가지 경우밖에 존재하지 않는다.
1) data[i-1]을 마지막 원소로 하는 연속부분의 끝에 data[i]를 추가하는 경우
2) data[i]가 처음이자 끝인 새로운 연속부분이 만들어진 경우
1)의 경우 그 값은 table[i-1]*data[i]가 되고, 2)의 경우 data[i]가 된다. 이 두 가지 경우 중에 최대가 되는 경우만을 택해 나가면 table[i]의 정의를 만족시킬 수 있다. 이를 토대로 점화식을 구하면 다음과 같다.
table[i] = max{ table[i-1]*data[i], data[i] }
이렇게 구한 table[i]중에 최대값이 바로 전체 수열 중의 연속 부분 최대 곱이 된다.
문제에 접근하는 방법에 따라 프로그램 수행 시간을 줄일 수 있다. 위의 문제는 N의 길이가 10000개가 들어오고 시간제한이 1초기 때문에, 채점 프로그램이 수행되는 컴퓨터 기준으로 3번째 solution 방법을 이용하여 문제에 접근하여야 합격(Accept)판별을 받을 수 있다.
대회에서는 출제자가 원하는 성능 이상의 알고리즘을 고안하여야 하며, 때문에 같은 정답을 받은 경시자들의 소스를 분석해도 접근하는 방법이 다를 수 있다.
|
※ 생각 할 거리
solution 3)의 방법에서는 배열을 이용하여 data와 table의 값을 채워 나갔다. 메모리 공간 효율성을 위하여, 배열을 사용하지 않고 프로그램을 작성할 수 있을까? |
- ACM-ICPC 공식홈페이지 : http://icpc.baylor.edu
- 서울 대회 공식 홈페이지 : http://acm.kaist.ac.kr
[저자 박일진 기자 약력]
- 06년도 23회 한국 정보올림피아드 경시부문 고등부 동상
- 07년도 정보과학영재교육 겨울캠프 강사진
- 08년도 ACM-ICPC Seoul Site 10th
- 08년도 8회 대학생 프로그래밍 경시대회 동상 (8위)
- 08년도 ACM-ICPC Hefei Site Bronze Medal
- 08년도 IT대학 소모임 SCCC 회장
- 09년도 교내 프로그래밍 경시대회 1위
- 09년도 ACM-ICPC Pucket Site 18th
- 09년도 ACM-ICPC Seoul Site 8th
- 09년도 9회 대학생 프로그래밍 경시대회 은상 (5위)
취재 : 박일진 기자(iljin7432@hotmail.com)
편집 : 김찬수 기자(kcsjhz@gmail.com)
http://www.comtimes.kr/news/309
기사에 대한 독자의견
독자의견 (총 0건)
Powered by Newsbuilder
