정보 올림피아드

2019. 6. 16. 15:23알고리즘 문제풀기/기타 주제

PS 용어 정리(링크)의 일부였던 글인데 길어져서 분리합니다.

"정올"이라고도 줄여서 부르는 정보 올림피아드(Olympiad in Informatics, OI)에 대해 소개하는 글입니다.

정보 올림피아드들은 형식과 문제 유형이 서로 비슷합니다. 때문에 정보 올림피아드에서 출제되는 문제 유형을 'OI 스타일'로 묶어서 지칭합니다. 대회 시간은 길고 문제 수는 적으며, 각각의 난이도가 높고 여러 단계에 걸쳐 생각을 발전시켜야 합니다. 스스로 고민해 풀이에 도달하는 과정을 중요시하기 때문에, 생각해 내기엔 지나치게 어려운 개념(플로우나 FFT 등)을 사용하는 문제는 잘 출제하지 않습니다.

 

국제 정보 올림피아드 (International Olympiad in Informatics)

공식 사이트는 오른쪽 링크에 있습니다. (링크)

세계 각국에서 선발한 국가대표가 매년 한 곳에 모여 치루는 PS 대회입니다. 1989년에 처음 개최되었고, 2019년 대회가 31회차입니다. 우리나라는 4회차인 1992년에 김하진 현 아주대학교 명예교수님이 이끄는 대표팀이 참가한 이래 늘 훌륭한 성적을 내고 있으며, 2002년에는 우리나라가 용인에서 직접 대회를 주최하기도 했습니다. 다음 주최는 언제가 될까요. IOI에 관한 세세한 기록은 모두 IOI statistics (링크) 페이지에 잘 정리되어 있습니다.

매년 이런 틀을 따릅니다.

  • 국가당 4명의 대표가 출전, 개최지에 머무름.
  • 일주일의 대회 기간 중 총 두 번의 대회.
  • 각 대회당 5시간 3문제, 각 문제당 만점 100점
  • 대회 중에는 다른 참가자의 점수나 현황을 알 수 없음
  • 동점자는 같은 성적으로 간주
  • 상위 50%의 참가자가 메달을 수상하며, 금:은:동=1:2:3의 비율

문제가 난이도 순으로 출제되는 해도 있고, 그렇지 않은 해도 있습니다.

IOI는 출제 가능한 문제의 범위를 명확하게 문서화해 공개하며 이 문서를 IOI의 실라버스(syllabus)라고 부릅니다. (링크)

문제의 서브태스크가 세심하게 나뉘어 있어, 만점 풀이를 떠올리지 못하더라도 부분 점수를 충분히 받을 수 있으며 그렇게 모은 점수가 때로는 문제 하나를 완전히 푼 것과 같은 역할을 하기도 합니다. 무엇보다 등수도 부분 점수에 의해 결정되는 경우가 많기 때문에, 할 수 있는 것부터 찬찬히 해 나가는 것이 중요합니다. 그리고 서브태스크를 하나하나 따라가다 보면 생각을 조금씩 발전시켜 나갈 수 있고, 만점 해법에 도달하기가 더 쉽습니다. 출제자들이 서브태스크를 통해 힌트를 주는 셈이지요. 어떤 값이 1인 경우, 그래프가 아니라 트리인 경우 등을 고민하면서 통찰을 얻을 수 있기 때문입니다.

세계 각국마다 무슨무슨 OI 하는 식으로 OI가 있으며 보통 각 나라의 IOI 국가대표를 선발하는 절차를 겸합니다. IOI는 출전 가능 범위가 대충 고등학생 이하(대학교육 미이수자)이기 때문에 각국 OI도 비슷한 수준으로 참가 자격을 제한합니다. 그래서 IOI에 출제되지 않는다고 명시된 개념들(플로우나 FFT 등)을 '고등학교 수준을 벗어난다'고 농담조로 말하기도 합니다. 고등학생으로서 몰라도 되는, 고등학생에게는 요구하지 않는 내용인 셈이라 그렇습니다.

ICPC 등의 대회와 다르게 스코어보드는 참가자 본인에게는 비공개로 진행됩니다. 남과 자신을 비교하는 데에 시간을 쓰는 대신 문제에 집중하라는 뜻입니다. 또 같은 점수를 받은 참가자 간에 제출 시간이나 횟수 등을 따지지 않고 무조건 같은 성적으로 시상합니다. 그래서 틀릴 걱정을 할 필요 없이 여러 번 제출해도 되지요. 할 수 있는 최대한 열심히 해 역량을 펼치기를 바라는, 어딘가 열정적이고 멋진 느낌이 있습니다.

국가 단위 OI 문제의 출제자는 나라를 불문하고 많은 경험과 이론적 기반이 있는 사람들이 맡는 듯합니다. 쉽게 말해 교수님들, 혹은 적어도 그 수준인 사람들이 맡습니다. 때문에 OI라고 하면 어느 정도 퀄리티가 보장되어 있다고 봐도 좋습니다. 그런데 그런 것 치고는 세계에 나라가 정말 많은데도 알려진 OI는 몇 없군요. 이 글에서는 보장된 퀄리티의 OI 몇 개만 소개하기로 합니다.

 

한국 정보 올림피아드 (Korean Olympiad in Informatics, KOI)

한국 정보 올림피아드(Korean Olympiad in Informatics, KOI)는 1984년 제1회 전국PC경진대회라는 이름으로 처음 개최되었습니다. 역사적으로는 IOI도 5년이나 앞서네요. 당시에 어땠는진 모르지만, 1996년 한국정보올림피아드라는 이름으로 개칭한 후 2019년까지도 이어오고 있는 이 대회의 문제 스타일은 IOI와 비슷합니다. 특이한 점은 4시간 4문제로 IOI보다 시간은 짧고 문제는 많습니다. 대신 문제가 난이도 순으로 주어집니다. (보장하지는 않지만 수십 년째 그랬습니다.) 또한 IOI와 다르게 동점자 간에는 제출 횟수 그리고 마지막 제출 시간으로 순서를 가릅니다. 국무총리상, 과기부장관상 등 등수에 따라 시상이 걸려 있는데, 이런 상의 개수가 처음부터 정해져 있어서 그렇다네요.

초등부, 중등부, 그리고 고등부로 나뉩니다. 전국대회 문제는 가끔 서로 겹치기도 하구요. 비교를 하자면 IOI는 고등부 전국대회의 어려운 문제들과 비슷하거나 더 어려운 정도입니다. 예전에는 전국대회를 매년 서로 다른 곳에서 개최해 전국을 순회했습니다. 천안, 춘천, 인천, 순천 등에서 대회가 열렸던 기억이 납니다. 그러다 최근 몇 년동안은 경산 경일대학교에서, 그리고 2018년에는 고려대학교에서 진행했습니다. 이때까지는 한국정보화진흥원(NIA)에서 주최해왔습니다.

2019년 KOI가 격변을 겪었는데, 저는 자세히 아는 내용이 없네요.

우리나라에서는 IOI 대표 선발은 KOI와 완전히 분리된 절차로 이루어집니다. 먼저 한국정보과학회가 운영하는 국제정보올림피아드 계절학교 교육생(링크)에 신청을 하고 시험을 치러 선발됩니다. 교육생은 여름과 겨울에 한 번씩 2주 동안의 계절학교 교육에 참가합니다. 그리고 매년 1-2월에 이루어지는 두 차례의 선발고사를 통해 IOI 국가대표 4명을 선발합니다. 선발고사도 역시 OI 스타일이구요. 계절학교가 교육과 선발의 기능을 겸하고 있고, KOI의 성적은 대표 선발에 아무런 영향을 주지 않습니다. 다만 최근에는 KOI 우수 성적자가 계절학교에 시험을 거치지 않고 입교할 수 있는 등의 제도가 생겼습니다. 계절학교는 대표가 되는 목적도 있지만, 대부분 전 대표 출신인 우수한 조교들에게 최고 수준의 교육을 받고 같은 분야의 친구들을 만들 수 있다는 점에서 참가할 수만 있다면 꼭 한 번쯤 참가할 만한, 좋은 제도가 아닌가 생각합니다.

 

일본 정보 올림피아드 (Japanese Olympiad in Informatics, JOI)

공식 사이트는 오른쪽 링크입니다. (링크, 일본어)

3시간 6문제의 예선과 4시간 5문제의 본선으로 이루어져 있고, 난이도순입니다. 12월에 예선, 2월에 본선이 치뤄지며 본선에서 우수한 성적을 받은 학생 20명은 3월(일본은 방학입니다)에 진행하는 봄 합숙(春合宿, spring camp)에 참가합니다. 봄 합숙에서는 무려 4일 연속으로 매일 5시간 3문제 대회를 치룹니다. 만점 1200점 기준으로 상위 득점자 4명을 추려 국가대표로 선발합니다. 부담감이 엄청나겠죠? (총 문제 수는 12문제 전후로 바뀌기도 합니다).

실력을 갖춘 사람이라면 JOI 본선은 할 만 합니다. 그런데 봄 합숙 문제는 상당히 어렵고 공부에 도움도 많이 됩니다. 2016/2017 시즌 봄 합숙부터는 일본어와 함께 영어 문제도 공개하고 있어 공부하기 훨씬 편해졌습니다. AtCoder에 대부분의 봄 합숙 문제가 채점 가능하게 업로드되어 있고, oj.uz에도 대부분 올라와 있어 어느 쪽을 쓰셔도 무방합니다.

선발한 일본 국가대표를 훈련하는 과정을 가지지는 않고, 통신교육의 목적으로 어느 하루를 잡아 5시간 3문제의 온라인 대회를 치룹니다. 그런데 열심히 준비한 대회를 고작 네 명만 치는 건 아깝잖아요? 그래서 전세계에서 참가할 수 있도록 JOI Open Contest(JOIOC)라는 이름으로 대회를 공개해 치룹니다. 여기 문제도 좋아요. 매년 영어 문제가 나오구요.

모든 문제는 위 링크에 올라와 있습니다.

 

아시아-태평양 정보 올림피아드 (Asia-Pacific Informatics Olympiad, APIO)

Olympiad in Informatics(OI)가 아닌 Informatics Olympiad(IO)라는 점이 재밌죠. 참고로 수학올림피아드에도 아시아-태평양 수학올림피아드(Asia-Pacific Mathematics Olympiad, APMO)가 있습니다. 공식 사이트는 오른쪽 링크입니다. (링크)

APIO에는 아시아 전역과 오세아니아의 국가들이 참가하며 돌아가면서 주최를 맡습니다. IOI처럼 한 장소에 모이기에는 비용 면에서 무리가 있겠죠? 그래서 이 대회는 온라인으로 진행합니다. 2박 3일 동안의 대회 기간 중, 각 나라마다 편한 시간을 정해 자국 참가자 모두가 한 장소에 모여서 5시간 3문제의 대회를 치릅니다. 그럼 우리보다 늦게 치는 나라에게 문제를 알려줄 수 있지 않은가 싶습니다. 실제로 가능한 건 맞습니다. 하지만 그러면 자기 등수를 깎는 셈이니 그러지 않지요. 대회 규정에도 모든 대회가 끝나기 전까지는 토론하지 말아달라는 조건이 있습니다.

대회가 끝나고 나면 IOI와는 다르게 대회를 친 모든 사람의 점수를 싣지는 않습니다. 대신 각 국가별로 대강 상위 6명만을 남깁니다. 그럼 6×(참가국 개수)명이 남겠죠. 실은 위에서 6번째 사람의 점수와 동점인 사람이 있으면 모두 남기기 때문에 그보다 많이 남습니다. 이렇게 남긴 사람들이 '공식 기록'이 되고, 이들을 국가 상관 없이 점수로 정렬해 공식 스코어보드 및 메달 순위를 결정합니다. 메달 기준은 IOI와 마찬가지로 상위 50%, 1:2:3입니다. 메달 역시 대회장에서 전달하지 못하니, IOI가 열릴 때마다 직접 만나서 상장을 전달한다는 점이 재밌습니다.

 

그 외

폴란드 정보 올림피아드(Polish OI, POI)가 있습니다. 역시 문제의 질이 좋기로 유명합니다. 짧아서 이해하기는 쉽지만 풀기는 어려운 그래프 문제를 잘 낸다는 개인적인 인상이 있습니다. 물론 그래프가 아닌 어려운 문제도 많습니다. 백준 온라인 저지(BOJ)에 많이 업로드되어 있습니다.

발칸반도 정보 올림피아드(Balkan OI)가 있습니다. 여기 문제도 좋습니다. 백준 온라인 저지(BOJ)에 많이 업로드되어 있습니다.
발트해 정보 올림피아드(Baltic OI)가 있습니다. 개인적으로 위의 발칸보다 약간 별로였던 것 같습니다.
많은 사람이 둘 중 한 쪽이 다른 쪽보다 낫다고 꼽는데 그게 어느 쪽이었는지 기억이 나지 않습니다. 발칸 반도와 발트 해 모두 BOI로 축약 가능해서 저는 늘 헷갈리네요. BkOI, BtOI 처럼 줄이면 나을까 싶긴 한데 이렇게 줄이는 건 본 적이 없어요.

중부유럽 정보 올림피아드(Central European OI)가 있습니다. 이쪽도 문제가 훌륭합니다.

'알고리즘 문제풀기 > 기타 주제' 카테고리의 다른 글

PS 대회 모음  (0) 2019.07.04
PS 용어 정리  (0) 2019.05.25
PS 계열 커뮤니티와 웹 사이트  (4) 2019.04.23
PS 토픽 모음  (1) 2019.04.21
CMS 세팅 (워커 등 분리)  (1) 2018.08.02