2020 군장병 코딩 경진대회 후기

학교 동기의 권유로 참가하게 되었다. 이렇게 제한시간 내에 문제를 풀고 코드를 제출한 것은 처음이었다. 이번 2020 군장병 코딩 경진 대회는 프로그래밍 대회를 모방하여 제한 기일 동안 군인인 참가자를 받아 코드를 제출 받았다. 나의 결과는 443명 중 15등이다.

후기

5문제 중 앞 3문제는 간단한 구현 문제였던 걸로 기억한다. 그리고 4번 문제는 최소 공통 조상(LCA)를 이용한 문제였다. 여기까지는 쉽게 해결했으나 5번 문제는 어려웠다. 5번 문제를 해결하는 과정에서 그래프내의 사이클 개수를 찾으면 될 줄 알고 문제를 풀어나갔다. 하다하다 tarjan의 SCC 알고리즘을 이용해 사이클의 수를 세었다. 하지만 tarjan의 SCC를 형성하는 알고리즘은 사이클의 크기가 최대가 되도록 형성하기 때문에 최소 크기의 사이클의 개수를 찾아야 하는 이 문제와 적합하지 않았다. 이는 물론 대회가 끝나고 깨달은 생각이다. 아마 해결 방법은 outdegree가 작은 것 부터 차례로 방문하는데 계속해서 모든 정점의 oudegree를 갱신해야 하는 것으로 예상한다. (아직 해결 방법을 확인하지 못했다.)

첫 프로그래밍 대회(?)였는데 나름 괜찮은 성적을 받은 것 같다. 마지막 문제를 제출하고 만점자가 많을 줄 알았는데 예상과 다르게 2명 밖에 없었다. 대회 1등이 전체 문제를 50분만에 해결한 것을 보니 역시 군인들 중에도 괴물은 존재한다는 것을 알았다. 아쉽게 3등 내에 들지 못해 상품은 얻지 못했다. 그래도 대회에 참가하니 조금 식었던 알고리즘 공부에 자극을 받았다. 3주 뒤 전역인데 사회에서 정말 열심히 해야겠다.