[IOI2009] Syllabus 분석

* 이 글은 제 21회 국제정보올림피아드와 관련된 글의 일부분입니다. 전체 글 목록을 보시려면 여기를 클릭하세요.


이전 포스팅에서 소개했던 IOI 2009의 Syllabus를 살펴보자면, 몇 가지 특징적인 점들을 발견할 수 있습니다.

• 동적 할당과, 이와 관련된 몇 가지 토픽들(Runtime storage management라거나 포인터라거나)이 모두 Not needed로 분류되어 있습니다. 즉, IOI에 한해서는 동적 할당을 사용할 필요가 없다는 이야기. 사실 IOI 문제에서는 항상 데이터의 크기 제한이 주어지니, 그만큼 정적으로 메모리를 할당해 놓고 구현하더라도 아무런 문제가 없습니다. Linked list와 같은 것들도 정적 메모리를 사용해 구현하기를 권장하는 것 같습니다. 정적 메모리를 이용한 linked list 구현 전략이 To be clarified로 분류되어 있네요.
• Floating-point numbers가 Excluded로 분류되어 있습니다. 아마 실수 오차를 잘 다루는 것이 어렵다는 이유로 범위에서 제외되는 것 같습니다. 사실 확률, 통계 부분은 모두 Excluded이므로 실수가 사용될 만한 곳은 기하 문제 정도가 있을 텐데, 그마저도 문제에 여러 가지 제약을 줘서 계산 과정에서 실수 연산을 사용할 일이 없도록 해 준다는 것 같네요. 혹은 설마 정수 두 개를 사용해 분수형을 만들어서 사용하라는 건 아니겠죠......
• 근사 알고리즘의 경우에도 이산 근사만 다루고 수치 근사는 다루지 않는다는 것이 흥미롭습니다. 이전 포스팅에서도 잠깐 언급했었지만, 근사 문제의 경우 주어진 finite한 값들 중 하나로 근사하는 유형의 문제만이 나온다는 의미겠지요.
• Fenwick tree의 경우 상당히 재미있는 성질을 가진 자료구조인데, 2000년대부터 올림피아드계에 소개되기 시작하더니(BOI던가에 이를 이용한 문제가 있었지요.) 2004년부터는 IOI에도 등장하고 있습니다. 제가 출전했던 2005년도에도 이를 사용하는 문제가 출제되었던 바 있지요.
• 기하 문제의 경우, 벡터 외적을 이용한 점들의 방향성 판단과 선분 교차 판단 정도만 잘 구현할 수 있으면 되는 것 같네요. 사실 실수 연산을 사용할 수 없으니 저 정도가 거의 가능한 한계겠지요.
• 유한 상태 기계와 context-free grammar 관련 내용이 지금은 Not needed로 분류되어 있지만, 조만간 Included로 변경될지도 모른다고 주석이 달려 있습니다. 아마 IOI의 출제 범위가 늘어나게 되면 가장 먼저 추가될 가능성이 있는 것 중 하나가 아닐까 하네요.
• 한국 학생들의 일반적인 정서와는 달리, maximum flow algorithm과 bipartite matching algorithm은 Excluded입니다. 애초에 이분 그래프도 Not needed로 분류되었던 바 있지요. Strongly connected component 역시 Excluded로 분류되어 있습니다. 특정 알고리즘을 외워야 풀 수 있는 문제를 가급적 지양하다 보니 그런 것 같네요.
• Heuristics가 Excluded로 분류되어 있는데, '설령 근사 문제가 나오더라도 만점을 받을 수 있는 결정적인(deterministic) 근사 알고리즘이 존재한다.'는 의지의 표현인 것 같습니다. 지금까지의 IOI 출제 경향도 그래 왔고요.