옛날 이야기이지만 - KOI 2016 (한국정보올림피아드) 후기

 

※ 주의!! 이 글은 너무 옛날 이야기를 소재로 하고 있습니다!!

 

※ 경고!! 이 글 작성자는 기억에 의존해서 글을 작성하고 말았습니다!!

 

 

옛날 옛적에...

 

정말로 개인적인 이야기로 시작하려다가 지웠다.

 

어쨌든 16년도에 고등부로 한국정보올림피아드를 나갔다. 몇 월이었는지는 까먹었다.

 

처음 나간 프로그래밍 ( 그 중에 알고리즘 ) 대회였다.

 

지역 예선이 필기 시험같은 형태로 하고

 

결선?이었나 그게 이제 당시 경일대학교에서 초등부/중등부/고등부 각각 200명씩해서

 

거기서 장려상 / 동상 / 은상 / 금상 뭐 그렇게 순위별로 주고,

 

상위 몇 명이었나 은상~금상 쯤이었나 그 정도 인원을 데리고 뭐해서

 

국제정보올림피아드 (IOI) 에 보내는 그런 식이었던 것 같다.

 

 

 

 

 

지역 예선

 

사실 시험 내용 자체는 잘 기억이 안 난다.

 

그냥 되게 매우매우 필기 시험같은 느낌이 물씬 나는 그런거였는데

 

C/C++ 프로그래밍 문법을 공부했다면 웬만해서 쉽게 맞추는 문제가 대부분

 

컷이 몇 점인지도 모르겠고, 되게 기본적인 문제로 이루어져있었고

 

무난하게 결선으로 가는, 기억에 잘 안 남는 그런 것이었다.

 

2017, 2018년도 얘기(추후 글로 또 써야지)도 지역 예선은 할 필요 없을 정도. 

 

 

 

 

 

결선

 

이게 메인이긴 하다.

 

진짜로 프로그래밍 대회라고 했을 때 느껴지는 그런 형식이니까.

 

1박 2일로 해서 첫 날이 약간 환경 확인하고 테스트하는 그런 시간이 있고,

 

그래서 둘째날에 시험만 보면 되는 그런거였지만

 

어쨌든 첫째날부터 있었다.

 

 

 

 

첫째날

 

경일대학교 체육관이었을 것이다.

 

거기에 600대의 컴퓨터가 널려있는 걸 생각해보면

 

지금 생각해도 뭔가 개쩌는 그런 느낌이었던 것 같다.

 

그렇게 많은 컴퓨터가 한 장소에......

 

 

그때 뭐 환경 체크하면서 주어진 테스트 문제가

 

90% 확신으로 색상환 문제였던 것 같다. (백준에 남아있고, 보아하니 2010년도 지역본선에 나왔다고 한다)

 

지금 보면 매우 잘 알려진 다이나믹 프로그래밍 문제라는 걸 알아차릴 수 있지만

 

당시에 알고리즘 응애였던지라 (고등학교 들어간 이후 코딩 시작함)

 

그거 결선 준비한다고 급하게 배운게 뭐더라

 

LIS, LCS, 0/1 knapsack (스펠링이 이거 맞나?) 막 그런거 어거지로 주입했는데 (이해하려고 노력은 했는데)

 

당연하지만 어거지로 주입하면 이해가 잘 안된다. 당시에는 그런 개념 자체가 어려웠다.

 

 

"어씨 이거 큰일났다"

 

 

본 시험 들어가서 한 문제라도 풀 수 있을까 바로 걱정이 되었다.

 

테스트 끝나고 기숙사 (대학교 기숙사에서 하루 묵는?식이었던 것 같다) 에서 밥 먹고 쉬고

 

그 "노란책"이었나 아닌가? 그거 17/18년도에 샀던가?

 

헷갈리는데 어쨌든 공부를 쪼끔하다가 과부화올거 같아서 쉬었던 것 같다.

 

 

 

 

둘째날

 

'둘쨋날'이 발음 생각하면 맞는 줄 알았는데, 찾아보니 '둘째날'이 맞다고 한다.

 

오늘도 하나 배웠다.

 

 

* 당시 문제들 모음집

https://www.acmicpc.net/category/357

KOI 2016

 

 

문제 목록을 보니 기억이 새록새록하다.

 

문제에 대한 내용 요약을 따로 하지는 않겠다.

 

그런건 나중에 따로 문제 푸는 방법에 대한 글로 써야지

 

 

1번. 리조트

 

아마 내 기억으로 여기서 부분 점수를 받고 그대로 장려상으로 끝났었던 것 같다.

 

부분 점수 자체는 푸는 방법을 몰라도 어떻게든 점수 0점이라도 안되게 해주는

 

그 정도였기 때문에...

 

 

위에서 말했다시피, 다이나믹 프로그래밍을 이해를 못해서

 

점화식조차 제대로 못 썼을뿐더러, 그런 생각도 못하고 아마 그리디 같은 방법으로 해결하려고

 

온갖 난리를 피웠던 것 같다.

 

그리고 결국 부분 점수라도 벌려고 어거지로 했다.

 

 

당연하지만, 지금은 개인적으로 매우 추천하는 초급 다이나믹 프로그래밍 문제라고 생각한다.

 

 

 

2번. 주유소

 

1번 부분 점수 얼추 받고, 못 풀 것이라고 생각은 했지만

 

어떻게든 점수를 쪼금이라도 더 벌어보려고 읽어봤던 것 같다.

 

나중에 보니 중등부에는 길이 일자로 되어있는 형태였지만

 

고등부는 일반적인 그래프 형태라는 것이 달랐다.

 

 

뭐 당연히 그렇지만 그래프 관련해서는 공부한 것이 없기 때문에

 

당연히 못 풀 문제였지만, 부분 점수 벌어보려고 생각은 했었던 것 같은데

 

결국에는 안됐지.

 

 

생각해보니 나중에 이 문제 시도를 해봐야겠다.

 

안 풀었네

 

 

 

 

3번. 트리

 

2번 얘기할 적에도 얘기는 했지만

 

그래프를 모르는 놈이 트리를 알고 있을리가...

 

그냥 문제 구경하는 셈 치고 봤다.

 

 

 

지금도 트리를 합칠 때 사용할 거는 알고 있지만

 

분할할 때 쓰는 테크닉은 아직 모른다.

 

몰?루

 

 

 

 

4번. 먼 별

 

지금도 이 문제의 내용에 대해서는 전체 내용을 기억하고 있다.

 

첫 대회의 가장 어려운 4번 문제같은 느낌으로 기억이 남았다.

 

시간별 별들 중 가장 먼 거리의 최솟값을 구하라는 문제인걸 보고

 

"이걸 어케품?" 하면서 장난아니네 했다.

 

구경은 참 잘했다.

 

 

지금 생각하면 한 시간에 대해 가장 먼 별의 거리는 컨벡스 헐에 회전하는 캘리퍼스로 구할텐데

 

문제는 그걸 시간별로 시간 초과없이 어떻게 구해야할지를 모르겠다.

 

 

 

 

 

대회 종료

 

보통 한 100점(한 문제당 100점) 받으면 동상은 받고 그러는데

 

1번 문제도 부분 점수로 긁은 입장에서 동상을 받으면 말이 안되지.

 

그래서 장려상을 받았다.

 

 

그래도 공부 기간에 첫 대회인걸 생각하면 선방했다고 생각은 한다.

 

그리고 그 이후 괴물이 너무 많다는 것을 느낀 기점이 되버렸다.

 

나도 괴물되고 싶은데 허이고 참 쉽지 않네

 

 

 

이상 옛날 이야기 하나가 끝났다.

 

ㅇ

 

 

여담 (정말 개인적인 쓸데 없는 이야기)

 

문제들을 복기하면 서 그런 생각이 들었다.

 

지금의 나는 과거보다 나아졌는가?

 

아마 머리에 든 것 자체는 그때보다 많아졌으니, 그러니까 플레 정도의 문제에 대한 글을 쓰고 있는걸테지

 

하지만 정말 그 문제를 풀 알고리즘 자체를 모르는 무지의 상태, 대회에 나온 문제들을 풀 때도

 

내 실력을 충분히 보여줄 수 있는가?

 

 

 

그러지 못할 것 같은 두려움에 빠진듯하다.

 

이 글을 쓰기 전에, 일종의 글을 쓸 트리거를 작동시켜준 아니메컵에서도

 

귀찮다는 이유로, 혹은 왠지 좀 빡셀거 같다는 이유로 문제를 넘겨버렸다.

 

뭐 물론 오히려 i번 문제였나 그거 풀고 싶어서 그런 것도 있지만

 

내가 생각을 좀 더 해보면 풀 수 있는 문제를 못 풀어서

 

지금의 나를 증명하지 못할까봐 의기소침해진적이 적지 않다고 생각한다.

 

 

 

증명이란 건 참 어렵다.

 

앞으로 몇 번의 고배를 더 마시려나

 

근데 이거 옛날 이야기할 거 더 많은데

 

하나 썼다고 이러면 어떡하냐

 

정말로 쓰레기통이 되어가고 있구만

 

 

 

계속 글이나 쓰면서 복습해야지

 

 

++

 

이거 글 쓰다가 아니메컵 2쿨한다는 걸 확인해서

 

급히 참가했는데, 그거 후기도 조만간 써야겠다.