제 4회 천하제일 코딩대회 본선 후기

몇 시간 전(2020년 12월 22일 7시) 제 4회 천하제일 코딩대회가 끝났습니다. 2학년 선배 두 분과 팀을 이뤄 참여했고, 11문제 중 5문제를 풀고 전체 4위로 동상을 받았습니다. 

 

원래 오프라인에서 진행되는 대회이지만 코로나19 상황이 악화되어 온라인으로 진행되었습니다. 팀원과는 디스코드로 소통했고, 부정행위 방지를 위해서인지 대회가 끝날 때까지 계속 캠을 켜고 화면도 공유해야 했습니다. 오프라인 행사를 기대했던 저는 아쉬움이 남았지만, 현재 상황에서 취할 수 있는 최선의 방법이었다고 생각합니다. 시작이 10분 연기되었던 점만 빼면 대회는 전반적으로 원활하게 진행되었습니다. 

 

처음에 디스코드 방으로 들어가니 딜레이가 너무 심하고, 마이크도 잘 되지 않는 것 같아 당황했습니다. 다행히 시간이 지나자 딜레이가 줄어들고 채팅으로 충분히 소통할 수 있었지만, 당황한 탓에 처음에는 문제가 눈에 들어오지 않았습니다.

 

문제 설명

문제는 A번부터 K번까지 총 11문제였으며, 이 중 B/D/E/G/K번 문제를 풀었습니다. 아직 백준에 문제가 올라오지 않아 기억나는 대로 대충 적어 보았습니다. 자세한 풀이는 이곳에서 확인하시기 바랍니다.

 

+ 문제가 올라왔습니다. 

 

A번 - 소리의 전파 관련된 문제로, 풀이를 보면 BFS 문제였던 것 같습니다. 문제 지문에 시그마 기호가 나왔는데, 덕분에 문제를 이해하지 못했습니다. 다른 팀들도 그랬는지 맞춘 팀이 한 팀 뿐이었습니다.

 

B번- 집의 지도가 이차원 배열으로 주어질 때 벽으로 변한다면 이어져 있던 공간이 둘로 나뉘는 점의 개수를 구하는 문제입니다. 그래프 이론에서 이러한 정점을 절점이라고 부른다고 합니다. 지도의 크기가 크지 않아 완전탐색으로 풀 수 있었습니다.

 

C번- 잘 모르겠습니다. 대회 중에는 한 팀만 풀었습니다.

 

D번- 매우매우 쉬운 사칙연산 문제였습니다. 불참한 팀을 제외한 모든 팀이 풀었던 문제입니다.

 

E번- 1515보다 작거나 같은 N이 주어질 때 1과 5로만 이루어진 N자리 자연수 중 15의 배수의 개수를 구하는 문제입니다. 무려 3차원 DP로 풀었는데, 정해와 매우 비슷해서 뿌듯했습니다. 조합을 이용해 풀 수도 있으며, 위 풀이 링크에서는 조합을 이용한 풀이만 설명하고 있습니다.

 

F번- 2000명 이하의 사람들과 이들의 친구 관계가 주어질 때 임의의 사람 a, b와 모두 친구 관계인 사람의 수를 찾는 쿼리를 최대 50만 번 수행하는 문제입니다. 쿼리마다 N명의 사람을 모두 탐색하는 시간초과 풀이만 생각나서 포기했는데, bitset stl을 쓰면 연산 횟수가 32배 줄어 풀 수 있다고 합니다. 시간복잡도에 상수를 붙여서 통과하는 경우는 처음 보았습니다.

 

G번- 문제는 잘 기억나지 않지만, 쉬운 문제였습니다. 초반에 당황한 탓에 3번이나 틀렸지만, 결국 전체 팀 중에서 처음으로 풀었습니다. 

 

H번- 최소 스패닝 트리(MST)에 xor을 끼얹은 문제였습니다. 대회 중에는 아무도 못 풀었습니다. 

 

I번- 서로 호출하는 함수들이 있을 때 함수를 모두 호출하기 위해 호출할 함수들을 고르는 문제입니다. Union-find, indegree 등등 뇌절했지만 제가 모르는 SCC 문제였습니다. 대회 중에는 한 팀만 풀었습니다. 

 

J번- 수학 문제였고, 거들떠보지도 않았습니다. 역시 대회 중에는 한 팀만 풀었습니다.

 

K번- 트리가 주어지며, 트리의 모든 정점마다 트리상의 두 정점을 골랐을 때 해당 정점이 LCA가 되는 경우의 수를 세는 문제입니다. 대회 초반에는 LCA만 보고 기겁하며 도망갔지만, 끝날 무렵에 다시 문제를 보니 정점마다 서브 트리의 크기를 구하면 풀 수 있는 문제였습니다. 대회 종료 10여분 전에 간신히 풀었습니다.

 

느낀 점

1등 팀은 사실상 정해져 있었기 때문에 3등까지 받을 수 있는 은상을 목표로 하였습니다. 결과를 보면 1등 팀은 10문제를 풀었으며, 각각 6문제, 5문제를 풀었던 2, 3등을 압도적으로 제쳤습니다. 저희 팀도 5문제를 풀었지만 페널티 차이가 너무 커서 아쉽게 4등 동상으로 대회를 마무리했습니다. 아쉽긴 하지만 풀 수 있는 문제는 모두 최선을 다해서 풀었기 때문에 미련이 남지는 않습니다. 선배들과 팀을 이루다 보니 민폐가 되진 않을까 걱정했는데, 1인분은 한 것 같아서 다행입니다. 

 

이번 대회는 예년과 다르게 2학기에 실시되어서 그런지 작년, 재작년 문제들보다 훨씬 어려웠던 것 같습니다. SCC, bitset 등 모르는 것들이 꽤 나오기도 했습니다. 아직 많이 배워야 한다는 사실을 다시 한 번 느꼈습니다. 

 

최근 solved.ac 랭작에 빠져서 수열과 쿼리 등 플레 문제를 많이 시도했는데, 이런 자료구조 기초문제만 풀다 보니 응용이 필요한 문제를 푸는 능력이 떨어진 것 같습니다. 직계 선배님도 플레 문제보다 오히려 골드 문제를 많이 푸는 것이 더 도움이 될 것 같다고 하신 만큼 이번 방학에는 다양한 응용 문제를 많이 풀어 보겠습니다. 

 

천코대가 끝나니 남은 일정이 없어서 1년이 끝난다는 것이 새삼 실감이 납니다. 간간히 백준도 풀고, 책도 읽고, 오늘 개막할 NBA도 챙겨보고, 겨울방학 프로젝트도 준비하며 느긋하게 연말을 맞이하겠습니다.