`22 현대모비스 알고리즘 경진대회 예선 후기

글을 쓰는 날짜 기준, 오늘(2022년 7월 1일) 오후 1시 30분부터 5시까지 약 3시간 30분 동안 `22 현대모비스 알고리즘 경진대회 예선에 참가했다. 문제 내용에 대한 언급은 서약 때문에 할 수 없어서 대회 환경에 대한 이야기를 해보려고 한다.

 

대회는 Goorm Devth(https://devth.goorm.io/)에서 진행됐다. 이 대회에서 가지는 몇 가지 특이 사항과 그로 인한 단점들, 응시하는 입장에서 주의해야 할 것을 적어보겠다.

07/14 추가) 아래 언급된 것 중 일부분은 본선에서 개선이 되었다. 본선에서 개선된 부분들은 별도 표시(*)를 해두었다.

 

1) 실시간 채점 X (*)

실시간 채점을 지원하지 않는다. 먼저, 다른 대회들의 진행 방식을 알아보자. 첫 번째로, 제일 많은 사람이 참가하는 것으로 알려진 Google Codejam은 실시간 채점을 반만 지원한다. Small set, large set이 있을 때, Small set만 결과를 알려주고 large set은 결과를 알려주지 않는다던지, 문제에 따라서 Large set까지 결과를 알려주는 경우도 있다. 두 번째로, KOI와 IOI 같은 경우 내가 학생이던 2010년~2012년을 기점으로 실시간 채점을 지원하기 시작했다. 그리고 다른 대부분의 대회에서 부분적으로라도 실시간 채점 결과를 알려준다. 실시간 채점이 도입된 이유는 여러 가지가 있지만, 가장 큰 이유로 코딩 실수로 인해 점수가 깎여 문제 풀이 능력이 높음에도 불구하고 낮은 점수를 받는 경우를 방지하기 위함이라고 개인적으로 생각한다. 즉, 실시간 채점은 최대한 응시자들의 실력을 여과 없이 보여줄 수 있는 수단이 된다는 것이다. 다만, 이 대회에서는 예제 데이터에 대해서만 채점 결과를 보여주고 나머지에 대해서는 대회 종료 3일 후에 결과를 공지해준다. 때문에 코딩을 하고 검수하는 과정을 거쳐서 점수가 나올 거라는 확신을 대회 중에 얻어야 한다. 다만, 아래 얘기할 몇 가지 특징 때문에 이도 거의 불가능하다.

 

2) 메모리 제한 언급 X, 스택 메모리 제한 언급 X

문제마다 시간 제한은 적혀있지만, 메모리 제한은 적혀있지 않았다. 그리고 스택 메모리 제한이 따로 있는지에 대해서도 언급이 없었다. 예선 대회 며칠 전 응시 환경 테스트로 나눠준 링크에 들어가서 테스트했을 때는, 스택 메모리 제한이 1MB 정도로 세팅되어 있는 것처럼 보였다. int argument 1개 있는 재귀 함수 깊이 10만은 잘 돌아가고 깊이 30만은 Segmantation fault 뜨는 정도였다. 이에 대해 공지가 없어서 1:1 문의하기로 질문한 결과 황당한 답변이 돌아왔다.

대화의 맥락을 해치지 않는 선에서 중간에 불필요한 내용은 편집음을 먼저 말한다. 결론은, 메모리 제한을 포함하여 스택 메모리 제한이 따로 있는지 여부 등 아무것도 얘기해줄 수 없다는 것이다. 이들이 말하는 이유는 응시자의 역량을 판단하는 주요 부분 중 하나이기 때문이다. 이게 응시자의 역량을 판단하는 주요 부분 중 하나인 것이 맞는지 틀리는지 여부를 떠나서 이로 인해 생길 수 있는 문제 상황에 대해 얘기해보겠다.

 

첫 번째로, 코딩하기에 따라서 메모리 사용량이 200MB, 400MB, 800MB 등 다양하게 나올 수 있는 문제가 있다고 하자. 메모리 제한이 얼마인지 모르기 때문에 풀이 과정 중 내가 생각할 수 있는 가장 적은 메모리 사용량을 가진 알고리즘을 구현해야 한다. 일반적으로 메모리 사용량이 적어지면, 실행 시간이 길어지는 trade-off가 있다. 시간제한은 문제에 명시되어 있지만, 가장 큰 데이터가 서버에서 얼만큼의 실행 시간을 가지는지 테스트해봐야 한다. 그런데 후술할 이유 때문에 이럴 수 있는 방법이 거의 없다시피 한다. 그리고 그렇게 해서 적은 메모리 사용량을 가지는 알고리즘을 구현했어도 서버에서 설정된 메모리 제한이 얼마인지 모르기 때문에 여전히 메모리 제한 초과일 수도 있다. 실시간 채점이 아니기 때문에 응시자는 대회 끝날 때까지 결과를 모른다. 다행히, 본선에서는 실시간 채점이 진행되어 이 부분에 대한 문제도 상당 부분 해결되었다. 코드를 제출해보고 메모리 사용량이 많다면 확인할 수 있기 때문에, 대회 중간 수정할 수 있다.

 

두 번째로, 스택 메모리 제한이 따로 설정되어 있다.

요즘 백준에서 쉬운 문제들을 이것저것 풀기 시작하면서 다른 사람들이 짠 코드들을 많이 보기도 하는데, 지역 변수로 variable-length array를 사용하는 코드들도 종종 보이고, 이것 나름대로 장점이 있어 나도 가능하면 이런 방식으로 코딩하고 있다. 다만, 스택 메모리 제한이 따로 설정되어 있기 때문에 variable-length array는 모조리 스택 메모리 영역에 올라간다. 그래서 크기가 100만인 int 배열 하나 잡으면 4MB로 스택 메모리 제한을 초과하게 된다! 이런 코딩 습관을 가지고 있는 사람들이 그 습관 그대로 코딩할 경우, 올바른 풀이를 가진 알고리즘일지라도 스택 메모리 초과로 낮은 점수를 받게 될 것이다. 다시 한번 말하지만, 실시간 채점이 아니기 때문에 대회가 끝나고 결과가 나올 때까지 이 사실을 모를 것이다.

이어지는 얘기로 재귀 호출도 조심해서 작성해야 한다. 예를 들어, 1000x1000 크기의 2차원 격자판에서 Flood-fill을 한다면, bfs와 dfs 두 구현 모두 가능한 게 일반적이지만, 스택 메모리 제한이 있는 이런 환경에서는 dfs를 사용하면 최악의 경우 recursion depth가 100만이 되어, 스택 메모리 제한 초과로 segmentation fault를 받을 수 있다.

 

마지막으로, 이 부분이 응시자들에게 공지되지 않았다. 나는 테스트 환경에서 테스트도 해보고, 1:1 문의하기를 통해 질문을 했기 때문에 저 정보들을 알고 의식하고 코딩을 할 수 있었는데, 과연 응시자 중 몇명이나 이와 같은 사항을 숙지하고 있었을까 의문이 든다.

 

3) 테스트 데이터 별로 점수 매기기

요즘은 많은 대회에서 ICPC 스타일로 AC or not을 하거나, IOI 스타일로 서브태스크를 둔다. 테스트케이스 별로 점수를 매기는 시스템은 정말 오랜만에 본다. 과거 KOI와 IOI는 테스트 데이터 별로 점수를 매겼다. 1)에서 이야기한 실시간 채점으로 넘어갈 때, 이 부분이 같이 바뀌었다. 서브태스크 제도를 채택하여, 서브태스크 안에 있는 데이터가 모두 맞아야지만 그 서브태스크에 해당하는 점수를 받을 수 있다. 1)에서 얘기한 이유와 마찬가지로 이 방법이 응시자들의 실력을 여과 없이 보여줄 수 있는 수단이 된다.

한 가지 예시로 테스트데이터 별로 점수 매기는 방법에 대한 문제점을 지적하겠다. 정해가 DP인 어려운 문제가 있다고 하자. 과거 KOI에서는 이런 문제를 못 풀 경우 다음과 같은 방법으로 최대한 많은 점수를 받기 위한 노력을 했다. N이 작으면 brute force로 풀고, N이 크면 그리디로 푼다. 이러한 방법은 문제에서 몇 점을 받을까? 결론은 테스트 데이터가 어떻게 구성되느냐에 따라 다르다. 문제 세터가 그리디를 저격하는 데이터를 몇 % 준비했는지에 따라 다르다. 만약, 그리디를 저격하는 데이터를 10%만 준비했다면, 이 코드는 90점 이상 받을 것이다.

이러한 문제는 서브태스크에서는 생기지 않는다. 만약, 그리디를 저격하는 데이터를 하나만 준비했더라도, N이 큰 서브태스크에 대해 0점을 받게 되기 때문이다.

문제점은 있지만 과거 KOI, IOI에서도 하는 방식이고 나름의 전략을 구현할 수 있어서 아쉬운 부분인 건 맞지만, 수긍할 수 있다.

 

4) 외부 IDE 사용 X, 오직 구름 에디터만 사용 가능, 구름 에디터 내부에서 복사/붙여넣기 불가능 (*)

외부 IDE 사용이 불가능하고, 오직 구름 에디터만 사용해야 한다. 그리고 구름 에디터 내부에서 복사/붙여넣기가 막혀있다. 이는 치팅을 방지하기 위함이다. 다만, 응시 환경을 매우 제한하는 조치로 소탐대실이다. 이로 인해 생기는 문제점은 매우 많다. 우선 구름 에디터 내부에서 복사/붙여넣기가 되지 않아서 일반적으로 코딩할 때 쓰는 복사/붙여넣기 조차 할 수 없다. 예를 들어, 한 코드 블록을 여러 개로 복제하고 싶을 때 그걸 일일이 손으로 다 쳐야 한다. main 함수에 있는 로직을 어떤 함수로 옮기고 싶다면, 마찬가지로 그 로직을 함수 안에서 직접 새로 타이핑해야 한다. 이 같은 조치는 응시자로 하여금 불필요한 시간을 들이게 한다.

외부 IDE 사용을 못하는 것도 많은 문제를 야기한다. 우리는 문제에서 시간제한이 몇 초인지 안다. 그러나 N = 100만처럼 큰 데이터에 대해 내가 작성한 알고리즘이 몇초 안에 돌아가는지 테스트할 수 있는 방법이 없다. 구름 IDE에서 테스트 데이터를 넣어볼 수 있는 기능이 있지만, N = 100만짜리 데이터를 만드려면 필연적으로 프로그램을 통해야 한다. 일반적인 대회 환경이라면 큰 데이터를 만드는 코드를 C++, Python 등으로 작성하여 넣어볼 수 있다. 그러나 우리는 구름 에디터 만을 사용해야 하기 때문에 큰 데이터를 직접 만들어서 넣어볼 수 없다. 즉, 내가 알고리즘을 작성해도 이게 시간 안에 동작하는지 테스트할 수 있는 방법이 없다.

 

5) 이상한 동점자 처리 기준

이 대회에서 동점자 처리 기준은 시험 종료를 얼마나 빨리 눌렀느냐이다. 보통 만점을 받을 것 같다는 확신이 있다면, 시험 중간에 시험을 종료할 것이다. 그러나 이런 동점자 처리 기준 때문에 만점을 받지 못해도, 본인이 남은 시간 안에 점수를 올릴 것 같다는 희망이 없으면 중간에 시험 종료를 하는 것이 등수에 유리한 조건이다. 그리고 여기서도 가장 큰 문제는 실시간 채점이 없기 때문에 현재 내 점수를 몰라 쉬운 문제에서 실수를 했는지 모른다는 것이다. 이런 상황이라면 보통 시간을 더 써서, 쉬운 문제 코드를 검증할텐데 동점자 처리 기준 때문에 취사선택을 잘해야 하는 웃픈 상황이 벌어진다.

 

본선에서는 실시간 채점을 지원했지만, 여전히 현재 동점차 처리 기준의 문제점이 남아있다. 예를 들어, 마지막 문제를 풀지 못했고 남은 대회 시간 안에 정해를 풀지 못할 것 같으면, 대회 시간 1시간이 남은 시점에서 시험 종료를 하는 것이 등수로 유리한 선택이 될 수 있다는 것이다. 이는 응시자에게 매우 가혹하게 다가온다. 과연 같은 점수를 받은 서로 다른 두 사람의 우열(등수)을 가리는데, 일찍 포기(시험 종료)한 사람이 더 잘했다고 할 수 있는가? 대회를 오래 준비해온 입장에서 생각해보았을 때, 일찍 포기한 사람이 더 높은 등수를 받는 것이 매우 이질적으로 느껴진다.

 

개인적으로 가장 선호하는 동점자 처리 기준은 NYPC에서 사용하는, 제출 횟수와 상관 없이 그 점수에 도달한 시각이 가장 빠른 순서다.

 

6) 미숙한 재채점 처리

대회 진행 도중 어떤 문제에 대해 수정 사항이 있었다. 문제 본문이나 예제 입출력이 수정된 것이 아닌, 응시자가 모르는 어떤 무언가가 수정되었다고 한다. 이 수정으로 인해, 그 문제를 이미 제출한 사람은 다시 제출을 해야 한다고 공지가 되었다. 길지 않은 3시간 30분 정도의 대회 시험 환경에서 상당히 여러 차례 공지가 있었다. 응시자 화면에서 공지가 잘 노출이 되는 곳은 가장 마지막으로 온 공지가 자동으로 노출되기 때문에 노트를 바라보며 문제 풀이에 집중한 응시자는 이 공지를 놓칠 수도 있다. 만약, 공지를 놓쳐서 그 문제를 다시 제출하지 않은 응시자가 받는 불이익은 어떻게 보상받는가? 대회를 진행하다 보면, 채점 데이터에 당연히 실수는 있을 수 있다. 그것을 비판하는 것이 아니다. 채점 데이터에 수정이 있더라도 응시자가 대회에 집중하는 흐름을 해치지 않도록 자연스럽게 재채점이 진행되어야 한다. 예를 들어, 이미 한번 재채점 공지를 본 응시자들은 대회를 진행하면서도 자신이 어떤 공지를 놓쳐 불이익을 받지 않을까 의식을 계속해야 한다. 그리고 가장 큰 문제점은 5)의 동점자 처리 기준 때문에 그 공지를 보기 전에 시험 종료한 응시자가 있을 수 있다! 그러면 그 응시자는 공지도 못 보고 다시 제출도 못하는데, 이와 같은 상황이 있어서는 안된다.

 

*) 결론

나는 2005년에 처음 KOI에 참가한 이후로 과도기도 직접 겪었고 아주 다양한 대회 환경에 참여, 세팅을 해봤었다. 그런데 이렇게 제한적이고 불편한 대회 환경을 경험해본 적이 없다. 실시간 채점이 아니기 때문에 반드시 필요한 랜덤 데이터 생성기를 작성하고 brute force 알고리즘과 답을 비교하여 검증하는 것을 할 수 없다. 큰 데이터를 만들어서 실행 시간을 측정해보는 테스트도 할 수 없다. 작은 반례 데이터 정도는 손으로 작성해서 넣어보고 답이 잘 나오는지 확인할 수는 있다. 재귀 호출 깊이가 깊어질 것 같으면, 재귀 호출을 이용한 풀이를 할 수가 없다. 혹은 직접 힙 메모리 영역에 스택을 구현하여 재귀 호출을 비재귀적으로 구현해야 한다. 메모리 제한이 공개되지 않았고, 실시간 채점이 아니기 때문에 알고리즘이 틀리지 않았더라도, 불필요하게 메모리를 많이 쓰면 500점 받을 사람의 결과가 300점이 되어있을 수도 있다.

과연 이와 같은 대회 환경이 응시자의 실력을 여과 없이 보여줄 수 있는 대회 환경이라고 할 수 있겠는가? 알고리즘 경진대회이기 때문에 자신이 작성한 알고리즘을 테스트해볼 수 있어야 하고, 틀린 게 스스로 확인된다면 디버깅도 해볼 수 있어야 한다. 지금 환경에서는 그것이 불가능하다.

 

환경은 대회 마다 다르다. 그것이 그 대회의 독특한 특징이 될 수도 있다. 예를 들어, KOI는 (내가 생각했을 때) 제출을 적게 하여 높은 점수를 받는 것이 실력을 판가름하는 데에 중요하다고 생각하여 제출 횟수를 동점자 처리 기준에 두었을 것이다. 과연 현대모비스는 일찍 포기(시험 종료) 하는 것을 실력을 판가름하는 데에 중요하다고 생각하여 이러한 동점자 처리 기준을 두었을지 의문이 든다.

 

IOI의 과도기인 IOI 2010, IOI 2011을 직접 경험한 입장에서 대회 환경이 성적에 미치는 영향이 매우 크다고 말할 수 있다. 물론, 잘하는 사람들은 환경이 어떻게 변하든 간에 좋은 성적을 받는다. tourist는 대회 환경이 대폭 바뀐 IOI 2010와 IOI 2011에서도 이전처럼 우승했다. 이 대회에서도 환경이 얼마나 불편하든 잘하는 소수의 사람은 여전히 좋은 성적을 받을 것이다. 다만, 그렇지 않은 사람도 적지 않다는 것이다.

 

끝으로, 대회를 망쳐서 감정적으로 작성하는 글은 아니다. 성적은 7/4 오후 2시 발표라 내 점수가 몇 점인지, 등수가 몇 등인지 아직 모른다. 다만, 지금까지 여러 대회에 참여했고 여러 대회를 준비한 입장에서 현재 환경에 대한 아쉬움을 매우 많이 느끼기 때문에 개선에 조금의 도움이라도 되길 바라는 마음으로 글을 적는다. 이 글을 어떤 사람들이 읽을지, 앞으로 현대모비스 알고리즘 경진대회가 어떻게 변할지 모르겠지만, 현재 환경은 명백히 최악이며, 개선할 여지가 매우 매우 많다. 알고리즘 대회를 아끼고 사랑하는 사람으로서 많은 사람들이 불편한 환경 때문에 대회를 즐기는 데에 방해가 되지 않길 바라는 마음이다.

---

7/10 추가)

본선 대회는 1) 실시간 채점이 아니었던 점과 4) 외부 IDE 사용이 불가능했던 점이 개선되었다. 이로 인해 응시자는 자신의 IDE를 사용하여, 시간초과 나는 코드를 짜서 랜덤데이터를 넣어 자신의 프로그램을 검증할 수 있고, 큰 데이터도 문제 없이 생성하여 테스트해볼 수 있다. 실시간 채점에서도 재미있는 부분이 있는데, 테스트케이스에 대한 결과는 알려주지 않고, 모든 테스트케이스를 통과한 경우 정답을 받았다고 알려준다. 또한, 모든 테스트케이스를 통과하지 않았더라도 각 테스트케이스에서 메모리 사용량, 실행 시간 등을 알려준다. 어떤 테스트케이스에 대해 시간초과인 경우 모든 칸이 빈칸으로 나오기 때문에, 시간초과 받았는지도 알 수 있다. 제출 횟수에 따른 패널티가 없다는 점을 이용하여, 중간중간 코드를 제출하여 준비된 채점 데이터에서 내 코드가 시간초과 나는지 쉽게 확인할 수 있다. 예를 들어, 문자열 N개가 주어진 문제에서 문자열을 $O(N \lg N)$으로 정렬하는 게 시간초과가 나는지 제출하여 쉽게 확인할 수 있다. 이러한 개선으로 인해, 응시자가 불필요하게 느끼는 불편은 대부분 해소되었다고 본다.

 

2) 메모리 제한 언급이 없는 점과 스택 메모리 제한이 작게 걸려있는 점, 3) 테스트케이스 별로 점수 매기는 점, 5) 괴랄한 동점자 처리 기준 등이 남아있긴 하지만, 종합적으로 생각했을 때, 남아있는 사항들은 현대 모비스 대회만의 특징으로 자리 잡을 수 있을 것이라 생각한다. 예상치 못한 빠른 피드백 반영에 조금 놀랐다. 내년에 열리는 대회는 어떤 플랫폼에서 어떤 특징들을 가지고 진행되는지 알 수 없지만, 만약 같은 환경으로 진행된다면 이 글에서 언급된 내용들을 토대로 대회에 알맞은 전략을 구성할 수 있을 것 같다.