2006 한국정보올림피아드 참가 후기

14년 반만에 작성한 한국정보올림피아드 후기

정보올림피아드는 2003년에 첫 참가해서 2006년에 처음으로 전국 대회에 진출했다.

정보올림피아드 대회 구성

2003년까지 정보올림피아드는

  • 교육청 대회
  • 시/도 대회
  • 전국 대회

와 같이 구성되어 있었다. 학교마다 다르지만, 교육청 대회에 진출할 학교 대표를 뽑는 학교 대회가 있는 학교도 있었다. 내가 다닌 중학교는 정보올림피아드를 준비하는 학생이 많았기 때문에, 학교 대회가 있었다.

교육청 대회는 각 교육청에서 하는 대회였다. 내가 참가했던 교육청 대회의 심사 방식은 현재와는 매우 다른 방식이었다. 심사위원이 지나가면서 말로 어떤 입력을 해야할지 알려주면, 그걸 내가 입력하고, 출력을 심사위원이 눈으로 보고 채점하는 방식이었다.

시 대회는 교육청 대회를 통과한 학생이 참가하는 대회이고, 여기서 상위권은 전국 대회에 진출했다.

2004년부터 2015년까지 정보올림피아드는 다음과 같이 구성되어 있었다.

  • 시/도 지역 예선 (필기)
  • 시/도 지역 본선 (실기)
  • 전국 대회

시/도 지역 예선은 필기로 여기서 통과한 사람은 시/도 지역 본선으로 진출했다. 필기에서 최고득점을 획득한 학생은 본선 대회에서 선서를 했다.

지역 본선과 전국 대회의 채점은 실시간이 아니고, 대회가 종료된 후에 제출하는 방식이었다. 2006년 지역 본선은 대회가 종료된 후 3.5인치 플로피 디스켓에 이를 담아서 제출했고, 전국 대회는 어떤 프로그램을 이용해 네트워크로 제출했던 것 같다. 참고로, 2006년에도 플로피 디스켓은 거의 안쓰는 장치였다.

2016년에 정보올림피아드의 주관 부처가 변경되었고, 대회의 구성도 모두 변했다.

2006년 정보올림피아드 시/도 지역 본선

당시에 고등학생이었기 때문에, 고등부에 참가했다.

대회 문제는 총 5개로 여기에서 풀어볼 수 있다.

1번 문제: 완전 제곱수for 만 이용해서 풀 수 있는 문제이다. 풀이는 여러가지가 있는데 아마도 이렇게 구현했을 것 같다.

  • M부터 N까지 모든 수에 대해서 완전 제곱수인지 검사

2번 문제: 영역 구하기는 모눈종이의 크기가 최대 100×100이기 때문에, 크기가 100×100인 배열을 만들고 문제에 나와있는 대로 배열을 채우면 된다.

문제의 설명은 원점이 왼쪽 아래이고, (x, y) 좌표가 (행, 열)을 의미하지 않지만, 이를 무시하고 배열로 생각하고 원점이 왼쪽 위, (x, y)가 (행, 열)을 의미한다고 가정하고 풀어도 문제 없다.

3번 문제: 내리막 길은 다이나믹 프로그래밍으로 해결할 수 있는 문제이다.

당시에 나는 다이나믹 프로그래밍을 재귀로 구현하는 법을 몰랐다. 재귀를 이용하지 않는 풀이로 위상 정렬을 이용하는 풀이가 있다. 인접하고, 높이가 낮은 칸으로만 이동할 수 있기 때문에, 이동할 수 있는 방법을 모두 그래프로 그려보면 DAG가 나온다. 이를 이용해 위상 정렬로 해결했다.

4번 문제: 동전 뒤집기는 담금짐 기법(Simulated Annealing)으로 풀 수 있는 휴리스틱 문제이다.

N ≤ 20 이면 모든 방법을 시도해 브루트 포스로 O(N22N)에 해결할 수 있지만, 이 문제는 N ≤ 32이기 때문에, 브루트 포스는 사용할 수 없다.

지역 본선에서 나는 랜덤을 이용한 지역 탐색을 이용했다. 지역 탐색을 조금 발전시키면 담금짐 기법을 만들 수 있는데, 당시에 담금질 기법의 이름만 아는 수준이었어서 대회가 종료된 후에 매우 아쉬웠다.

5번 문제: 트리분할은 트리에서 다이나믹 프로그래밍을 이용하는 문제이다.

대회 당시에는 이 문제가 다이나믹 프로그래밍인 것을 몰랐고, 당시에 내가 풀 수 있는 가장 어려운 트리 다이나믹 문제는 2213번: 트리의 독립집합이었다.

당시 선택한 전략은 N이 작은 경우에는 브루트 포스로 답을 구하게 해놓았다. 아마 N ≤ 10에 브루트 포스를 사용했을 것 같다.

N이 조금 커지면, 백트래킹을 이용했다. 적절한 커팅 사용으로 답을 열심히 구하게 했다. N이 조금 더 커지면, 백트래킹의 결과에서 지역 탐색을 시작하게 했다. 대회 당시 시간 제한이 몇 초였는지 기억은 안나지만, 시간을 계산하는 함수를 이용해 시간 제한이 되기 0.1초 전에 프로그램을 종료해 답을 출력하게 했다.

두 문제에서 지역 탐색을 사용했기 때문에, 큰 기대를 하지 않았다. 문제의 난이도가 어려워 모두 다같이 4, 5번을 만점에 해결하지 못해서 전국 대회에 진출했던 것 같다.

2006년 정보올림피아드

2006년 정보올림피아드는 7월 14일에 백범김구기념관에서 열렸다. 당시 사진을 3개 찾았고, 아래 사진은 단체 사진의 윗 부분을 잘라서 올렸다.

확실하지는 않지만 2006년 정보올림피아드부터 은상, 동상의 수상 인원이 대폭 늘어난 것으로 기억한다. 2005년까지는 대상, 금상, 은상, 동상이 1, 1, 3, 5명이었던 것 같은데, 2006년 부터 대상, 금상이 1, 3명으로 은상, 동상의 인원이 매우 많이 늘어났었다.

대회의 배점이 1, 2, 3번 순이 아니고, 1, 3, 2번 순이었다.

1번 문제: 기지국은 다이나믹 프로그래밍 문제이다.

N ≤ 10,000 이라서 O(N2)을 하면 시간 초과가 날 것 같지만, 실제로는 통과할 수 있다. 당시는 2006년이라 확신이 없었지만, 부분 점수를 얻을 생각으로 다이나믹 프로그래밍을 구현했다.

지금은 정사각형 통신 범위를 구하는 것이 어렵게 느껴지지 않지만, 대회때는 까다로웠던 것 같다.

2번 문제: 두부 모판 자르기도 다이나믹 프로그래밍 문제이다.

대회를 준비하면서 풀던 문제 중 6569번: 몬드리안의 꿈이 있었고, 이 문제와 풀이가 유사한 문제이다.

N×M 격자판에서 1×2, 2×1 격자로 나누는 문제는 두 가지 시간 복잡도 O(N22M), O(NM2M) 로 해결할 수 있는데, 당시에는 O(N22M)만 구현할 수 있었다.

이 문제는 1×1도 가능하기 때문에, O(N22M)으로는 해결할 수 없었다. 정확하게 어떻게 구현했는지 기억은 나지 않지만, 다이나믹을 이용해서 구현한 것 같다.

3번 문제: 마법 구슬은 분할 정복 문제이다.

보통의 분할 정복 문제는 N개를 가운데에서 나눠서 한 쪽 N/2개, 다른 쪽 N/2개로 나누지만, 이 문제는 안 쪽 N/2개와 바깥 쪽 N/2개로 나눠야 하는 문제이다.

이 문제는 문제를 보는 순간 해결할 수 없다는 것을 알았다. 입력이 독특한데, 가능한 (N, M) 조합의 개수가 21 + 22 + … + 213 = 214 – 2 = 16382개이다.

작은 N에 대해서 백트래킹을 구현해보니 답이 빠르게 나왔지만, N이 조금 커지니 특정 (N, M) 의 조합에서는 답이 빠르게 나오지만, 거의 대부분의 (N, M)에서는 답을 구하는데 매우 오래 걸리거나, 답을 구할 수 없었다.

대회 시간 동안 백트래킹을 돌려두고, 코드를 출력하는 코드를 작성했다.

중간 중간 프로그램을 중단해 어딘가에 백업을 해두었고, 답을 오랜 기간 구하지 못하면 종료하게도 만들었던 것 같다.

당시 구현한 프로그램을 간단히 아래 글에 정리해 놓았다.

2006년 정보올림피아드 대회 결과

대회가 종료되면 어떤 프로그램을 실행해 네트워크로 소스를 제출했다.

대회가 종료된 후에 시간이 꽤 오래 지나면 결과를 프린트로 출력해 나누어주었다. 기억으로 1번은 1, 2개 빼고 점수를 얻었고, 3번에서 꽤 많은 부분 점수, 2번에서는 절반 수준의 부분 점수를 얻은 것 같다.

은상을 받게 되었다. 사람들과 결과를 비교해보니 몇 점을 더 얻었으면 금상을 받았을 수도 있을 것 같았다.