d라이브러리

처음 참가하여 비교적 높은 성적을 거두었으나 실제 실력이 상위권이라고는 결코 말할 수 없다. 컴퓨터가 정식 교과목으로 자리잡지 못하고 결과 위주의 교육이 계속되는 한 다음 대회에도 좋은 성적을 거둔다는 보장이 없다.

국제 정보올림피아드(IOI, International Olympiad in Informatics)는 만 20세 미만 대학교육 이전의 학생을 상대로 세계 여러 나라 학생들이 참가하여 각자의 컴퓨터 실력을 겨루는 대회다.

올림피아드 대회는 정보 올림피아드 뿐만 아니라 우리가 잘 알고 있는 수학 올림피아드를 비롯, 물리 화학 생물 등 모두 5개가 있다. 이 대회들은 유네스코 산하단체인 각 분야의 연합회에서 주관하기 때문에 그 분야가 다른 데도 불구하고 대회운영 등 여러가지 면에서 많은 공통점을 가지고 있다. 이러한 공통점은 예전에 수학 올림피아드가 소개 될 때 대부분 언급되었기 때문에 이 글에서는 IOI의 특징에 대해서만 설명하겠다.

먼저 IOI의 역사에 대해 알아보면 유럽 중심으로 열린 89년 헝가리 대회가 처음이고, 옛 소련, 그리스를 거쳐 이번에 독일에서 열린 대회가 네번째로 올림피아드 중에서는 두 번째로 막내동이다(가장 막내동이는 생물 올림 피아드).

그러나 컴퓨터의 빠른 보급과 더불어 해가 거듭될수록 더 많은 나라에서 참가하여 이번 대회에는 52개국이 참가하고 46개국 학생들이 시험을 치렀다. 여전히 유럽쪽에 치우치기는 했지만 아시아와 아메리카쪽에서 많은 나라들이 새로 참가하여 1백69명의 학생이 시험에 응시, 전세계적인 대회로서 틀을 조금씩 잡아가고 있다.
 

「결과」보다 「과정」을 중시

대회 진행은 하루 1문제에 5시간씩 이틀간 치러진다. 그리스 대회까지는 이틀 연달아 시험을 치렀는데 이번 대회는 하루 걸러 시험을 치렀다.
여기서부터 우리나라 시험이나 대회하고 현저한 차이가 난다. 우리나라의 경우 컴퓨터가 정식 과목이 아니어서 시험을 보지는 않지만 필자의 경우 과학고등학교에 다니고 있기 때문에 학교에서 컴퓨터 교육을 받고 있다. 우리나라 컴퓨터 시험은 50분에 20문제 이상을 풀도록 요구한다. 또 전문적인 컴퓨터 대회에서도 예선에서 이러한 시험을 치르며 본선에서도 3시간 동안 5문제나 풀 것을 요구한다.

이 때문에 지금까지 국내 컴퓨터대회에 출제되었던 문제를 보면 깊은 사고를 요하는 것보다는 단순한 작업의 연속인 경우가 많았다. 요즘 들어 많이 바뀌기는 했지만 3시간에 5문제를 풀도록 요구하는 환경 아래에서는 한계가 있게 마련이다.

컴퓨터 프로그램을 짠다는 가장 기본적인 사실이야 다를 바 없지만 논리적인 구성과 창조적인 발상, 문제에 대한 정확한 이해와 분석력이 요구되는 문제라는 점에서 우리가 알고 있는 여러가지 대회에서 출제된 문제의 성격과 판이하게 다를 수밖에 없는 것이다.

국내 대회에서 문제를 해결하는 방법이 이미 완성된 설계도와 지침서에 따라 일을 하는 과정이라고 한다면, IOI가 요구하는 것은 하나의 주제에 맞도록 설계도를 작성하는 일이라 할 수 있다. 여기서 '완성'이라 하지 않고 '설계도'라 한 것은 그럴만한 이유가 있다.

국내에서 시험이나 각종 대회는 그 결과를 중요시한다. 객관식 시험이 그 대표적인 예다. 그러나 IOI는 그렇지 않다. 비록 프로그램이 제대로 작동하지 않아도 프로그래머의 기본적인 방향과 아이디어가 옳다면 그에 상응하는 점수를 부여하고 있다.

결국 IOI는 주어진 과정을 그대로 수행하는 것을 요구하는 것이 아니라 하나의 일을 처리하는 데 있어서 스스로 그 과정을 세우기를 요구하는 것이다. 그러면 IOI 문제의 출제경향을 소개해 보도록 하겠다.
 

실용적인 문제가 출제빈도 높아

우선 각각의 요소와 그 요소들간의 관계를 따지는 그래프(graph) 문제가 많이 등장 한다. 여기서 그래프란 수학에서 말하는 좌표평면상의 그래프가 아니다. 컴퓨터에서 그래프란 특수한 관계로 엮어진 요소들의 집합이다.

이러한 그래프 문제는 특히 동구권이 강세를 보이고 있다. 그러나 그래프 문제가 수학에서 말하는 조합론과 연결되면 수학적 지식이 많이 요구되므로 문제 자체가 굉장히 어려워지기 때문에, 출제문제 후보로는 자주 올랐지만 실제로 출제되는 경우는 별로 없었다.

두번째 평면상에서의 위치를 다루는 지리적 알고리즘(Geometric Algorithm)문제가 상당히 높은 빈도의 출제율을 보인다. 이런 문제는 보통 사람은 아주 쉽게 풀 수 있지만 컴퓨터로 구현하기 어려운 경우가 대부분이다.

예를 들어 보면 평면상에 수많은 점을 주고 가장 가까운 두 점을 찾으라는 문제도 있을 수 있고, 주어진 점들을 둘러싸는 볼록 다각형을 만들라는 문제도 있을 수 있다. 이런 문제들은 사람의 경우 한번에 전부를 보기 때문에 쉽게 찾을 수 있지만 컴퓨터로 구현하려고 하면 많은 생각을 해야 한다.

실생활에서의 컴퓨터 이용이 점점 더 강조되고 있으므로 이런 부류의 문제는 계속 출제되리라는 예상이다.

역시 실생활과 관련이 있는 문제라고 할 수 있겠는데 바로 스케줄(schedule)문제다. 가령 우리나라는 철도 노선이 상행선과 하행선 두가지 밖에 없다. 이럴 경우 통일호 무궁화호 새마을호 등 여러가지 기차의 종류를 주고 각각의 기차들에 대한 출발 시각을 결정하는 문제같은 것도 있고 어떠한 것을 이루기 위해서 가장 최소로 무엇을 어떻게 하면 될지를 결정하는 문제 등 일상 생활에서 우리가 계획을 세우는 모든 것을 다 포함하는 문제다. 이번 대회에서도 두번째 문제로 스케줄 문제가 출제되었는데, 이런 종류의 문제는 아이디어뿐 아니라 여러가지 프로그래밍 기법도 요구하므로 상당히 즐겨 내는 문제중의 하나다. 마지막으로 우리가 흔히 즐겨 하는 퍼즐문제를 들 수 있다. 3x3이나 4x4로 구성되어 있는 그림맞추기 퍼즐이나 동전을 갖고 이리저리 옮기면서 똑같은 모양이 전부 같은 쪽으로 오게 하는 등의 문제, 그리고 숫자를 부르는 게임이라든지 칸을 채우는 게임 등 다양한 문제가 있다. 이러한 문제는 스케줄문제와 마찬가지로 아이디어와 프로그래밍 기법을 동시에 요구하기 때문에 많이 출제된다.

대회참가와 입시, 이중부담

개략적으로 IOI 문제의 경향을 살펴 보았는데, 이번에 처음 참가하는 우리에게 이런 문제들은 생소할 수밖에 없었다.

비록 이번에 우리나라가 4위라는 좋은 성과를 거두었지만, 참가 선수 4명 전부 고등학교 2학년이고 예상했던 출제 경향과도 비슷한 데다 운까지 따라 주었기 때문에 이러한 성적이 나온 것이지 실제 실력을 정확히 비교한다면 결코 상위권이라고는 말할 수 없다.

그 이유를 짐작하는 것은 어렵지 않다. 우리나라의 경우 컴퓨터는 정규 교과목이 아니다. 학원이나 학교 특별활동 시간에 제한된 교육을 받을 수밖에 없는 환경에서 우리나라 학생들의 컴퓨터 실력이 올라가리라 기대하는 것은 지나친 욕심이다. 컴퓨터의 중요성을 누구나 인식하면서도 정식 교과목으로 넣지 못하는 이유는 다른 과목 견제 때문이라고 한다.

외국의 경우 오래전부터 컴퓨터가 정식 교과목이 되었다. 흔히 우리보다 못하다고 생각하는 태국의 경우, 고등학교에서 컴퓨터에 관련된 과목이 7개나 있어서 자신이 선택하면 그 모든 과목을 다 배울 수 있다고 한다.

동구권 나라들은 영재교육 그 자체를 세분화해 컴퓨터 전문 고등학교가 있으며, 이것은 우리나라 컴퓨터 전문학교와는 성격이 달라 아주 높은 수준의 컴퓨터 과학을 공부한다고 한다. 따라서 우리나라가 학원에 의존한 절름발이 컴퓨터 교육을 계속하는 이상 앞으로 올림피아드에서 더 좋은 성과를 기대하기는 어렵다.

그리고 이것은 비단 IOI 뿐만 아니라 모든 올림피아드에 해당하는 얘기인데, 우리나라에는 올림피아드에 대한 사회적 기반 조성이 너무 미흡하다. 심지어 주변에서 "대학입시에 안 나오는 컴퓨터를 뭣하러 공부하느냐"는 말도 들은 적이 있다.

바르셀로나 올림픽이 진행되는 동안 매스컴은 종일 올림픽에 관해서 말했고 사람들의 관심도 전부 그쪽으로 쏠렸다. 그러나 헝가리에서 스포츠 중계를 하듯이 수학경시대회를 중계방송한다고 얘기하면 아마 이상하게 들릴 것이다. 그만큼 헝가리에서는 각종 경시대회에 관한 국민들의 관심이 높다.

이런 정도의 관심을 바라는 것은 아니지만, 백년대계라는 교육보다 영화나 스포츠에 더 많은 관심을 가지고 있는 사회적 분위기에서는 우리 학생들 뿐만 아니라 그동안 계속 도와주신 교수님들이나 다른 분들이 의욕을 갖기가 어려울 거라고 생각한다.

우리 나라를 외국과 비교하는 그 자체가 무리일 수도 있겠지만, 우리가 아직도 후진국이라고 생각하는 중국의 경우에 경시대회에 대한 관심은 엄청 높아서 국내의 경시대회에 입상을 하거나 국제대회에 출전하는 것이 개인의 가장 큰 명예중의 하나로 인식되고 있다.

이렇게 사회적 기반이 조성된 후에 따르는 것은 당연히 이런 대회에 대한 지원이다. 중국의 경우 국제 대회에 출전만 해도 속된 말로 평생동안 '팔자'를 고친다. 각 분야의 대표로 뽑힌 학생은 그후 어떤 것에도 구속당하지 않고 그 과목을 공부할 수 있고 대학 진학은 본인 의사에 따라 결정된다. IOI의 경우 한 문제당 5시간인데 중국 학생에게 물어보니 그런 문제를 수천문제를 풀었다고 한다.

대학 입학생을 내신과 추천에 의존하는 미국을 비롯한 서방 국가들은 올림피아드 선수들에게 특별한 배려로 그들이 원하는 대학에 쉽게 진학할 수 있게 하고 있으며, 베트남에서는 학교 경시대회에서 성적이 우수한 학생들에게도 상급학교 진학에 특전을 부여한다고 들었다.

올림피아드에 출전할 정도라면 적어도 그 과목 만큼은 성적이 우수하고 대학에서 그 과목을 훌륭히 소화해 낼 사람이 틀림없음에도 불구하고 이번 우리나라 대표단은 거의 전부가 대학입시에 쫓겨 이중의 부담을 져야만 했다.

필자의 경우 과기대를 진학하기 때문에 특전이 있었지만 고3 선배들은 대학진학에 신경을 쓰는 모습이 역력했다. 충분히 대학에 합격할 선배들이지만 암기과목 같은 것에 쫓겨 올림피아드 준비에 힘들어 하던 모습이 기억에 남는다. 마지막 정리를 해야 할 기간에 기말고사 때문에 제대로 정리도 못하고 떠나면서 출국하는 비행기 안에서야 비로소 대회 걱정을 하는 것을 보고 안스러운 생각이 들었다.

정보 올림피아드 문제 예

둘째날 문제) 등반문제
등산가 클럽에 P명의 인원이 1부터 P까지 번호가 매겨져 있다. 모든 멤버는 동일한 속도로 등반하며 위쪽 혹은 아래쪽으로 이동하는 속도는 같다. i번째 등반자는 1일당 C(i)개의 소모품을 소모하며 최대 s(i)개의 보급품을 가지고 갈 수 있다. C(i)와 S(i)는 모두 정수다.

충분한 보급품을 가진 한 등반자가 산의 정상에 도달하는 시간은 N일이라 가정하자. 산의 높이가 너무 높기 때문에 한 사람이 가진 보급품만으로는 정상에 도달할 수 없다. 따라서 몇 사람의 인원으로 이루어진 그룹이 동일한 시간, 장소에서 출발한다. 정상에 오르기 전에 한 등반자는 다시 내려와서 자신의 불필요한 보급품을 다른 등반자에게 넘겨 준다. 등반자는 등반기간 동안 휴식을 취할 수 없다고 가정한다.

해결해야할 문제는 등반 클럽의 일정을 정하는 것이다. 적어도 한 사람의 등반자는 정상에 도달해야 하며 선택된 그룹의 모든 인원은 출발 지점으로 되돌아 와야 한다.

다음의 과정을 수행하는 프로그램을 작성하라.

1. 정상에 도달하는데 필요한 날짜 수인 정수 N과 클럽 내의 등반자 수인 정수 P 그리고 1부터 P까지의 모든 등반자들에 대하여 각각 S(i)와 C(i)를 키보드로부터 입력 받는다. 입력 값은 정수로 하고 허용되지 않는 수는 무시한다.
2. 등반 일정을 찾는다. 등반에 소요되는 가능한 그룹내의 등반자 a(1)……a(k)를 결정하고 1부터 k까지의 j값에 대해서 등반자 a(j)가 출발 지점에서부터 나를 수 있는 보급품 수인 M(j)를 결정하라. N,S(i) 및 C(i)의 모든 조합에 의한 일정에서 가능하지 않은 경우도 있음에 주의하라.
3. 다음의 정보를 출력하라.
a) 등반에 실제로 소요되는 인원수 k
b) 등반에 필요한 전체 보급품의 수
c) 클럽 내의 등반자 번호 a(1)……a(k)
d) 1부터 k까지의 값 j에 대해 등반자 a(j)가 출발 지점에서 나를 수 있는 보급품량 M(j)
e) 등반자 a(j)가 다시 내려오기 시작하는 날짜 D(j)
4. 다음의 조건에 해당하면 일정은 최적이 된다.
a) 등반에 참가하는 인원수가 최소다.
b) 조건 a)를 만족하는 그룹 중에서 소모되는 보급품 양이 최소인 그룹
최적의 일정에 근접하는 결과를 찾아라.

<;기술적 제약 조건>;
조건-1. 문제 해결 프로그램은 "C:＼IOI＼DAY-2＼422-PROG.xxx"라는 이름으로 아스키 파일 형태로 저장 하고 확장자는 .BAS, .C, .LCN(LOGO program), .PAS로 하라.

조건-2. 다음의 조건에 해당하면 입력을 허용하지 않는다.
-N이 1보다 작거나 100보다 크다.
-P가 1보다 작거나 10보다 크다.