제6회 GBS Coding Contest 후기

2021년 1월 7일에 열렸던 GBS Coding Contest(이하 GCC)의 후기를 늦게나마 적어보려 한다. 사실 블로그를 개설하기 이전의 이야기라서 이걸 올려야 하나... 여러 번 고민했다. 그래도 내가 살면서 대회 후기글을 얼마나 써볼까 싶기도 하고 다음 대회의 개최에 참고하기 위해서 글을 써본다.

 

GCC는 교내 알고리즘 동아리 ALPS에서 주최하는 대회이며, 전 학년에서 참가자를 받는다. 이번 대회는 14기 선배분들이 총 10문제를 출제해주셨고, 모두 코드업(2806~2815)에서 볼 수 있다. 다시 한번 문제를 출제해주신 선배님들께 감사의 말을 전합니다!

 

나는 4시간 동안 6문제를 해결하였고, 1등과 2등도 각각 6문제를 풀었으나 페널티 차이로 3등을 차지했다. (상품으로 키보드를 받았는데, 무려 SCPC 2020 로고가 찍혀 있었다(!!!) 귀한 키보드를 선물해주셔서 감사합니당)

1등하신 선배님과 2등한 컵이 축하합니다 ㅎㅎ 그리고 대회에 참가하신 모든 분들 수고하셨습니다!

 

 

~0:00

 

줌에 접속하고, 대회 화면과 codeblocks를 세팅했다. 노트북을 너무 막 써서 그런지, 내 노트북은 줌에 들어가기만 하면 느려진다. 덕분에 줌에 접속하고도 계속 끊겨 안내사항을 듣지 못했다.

 

 

~0:01

 

대회가 시작되었는데, 정작 문제가 열리지 않았다. 새로고침을 여러 번 시도하였지만, 성과가 보이지 않아 엄청 당황하였다. 다행히 코드업을 나갔다 오니 문제가 보였고, 빠르게 코딩을 시작했다.

 

 

~0:04

 

A번을 보자마자 노솔 방지 문제라는 확신이 들었고, 9로 나눈 몫과 나머지를 이용한다는 관찰을 통해 빠르게 퍼솔을 따냈다. 수식을 세우고 적당히 관찰만 하면 풀리는 깔끔한 문제였다. (사실 퍼솔 욕심에 식 대충 쓰고 코너 케이스 나오길래 바로 제출했다.)

 

컴퓨터 2실의 iMac

 

~0:17

 

B번은 문자열이 나와서 일단 거르고, C번은 dp 같은데 문제 이해가 어려워서 넘어갔다. D번은 해볼 만하다는 생각이 들어 예제를 봤는데 공차가 주어지니 모든 Ai를 A0에 맞추고 최빈값의 개수를 세어주면 풀린다는 게 바로 보였다. map을 이용해 빠르게 구현하였고 제출했으나 WA...  뭐지? 하고 보니 최빈값의 개수를 그대로 출력했더라. N에서 빼주니 AC.

개인적으로 이번 대회 문제 중 가장 심플하고 아이디어가 예쁜 문제였다.

 

낙서 고치기

 

~0:23 (여기서부터는 퍼솔이 아니라 시간이 정확하지 않다. 참고만 하자)

 

스코어보드를 쓱 보니 내가 가장 위에 있었고(이때까지는 내가 1등 할 줄 알았다) B번이 풀려서 다시 B를 잡았다. 처음에는 시간복잡도를 획기적으로 줄여서 문제를 그대로 구현하면 되는 줄 알았는데 그러면 이렇게 빨리 풀릴 리가 없다고 생각했고, 다시 관찰해보니 대표 문자열 중 사전 순으로 가장 앞선 문자열의 길이는 항상 1이더라. 문제에 감탄하며 빠르게 구현 후 AC.

 

대표 문자열

 

~0:45

 

E번이 재미있게 생겨서 잡았고, 수많은 사고력 문제의 경험으로 k번째 퍼즐 조각을 k-1번째 퍼즐조각 4개로 채울 수 있다는 것을 이용하는 문제라고 생각했다. 이를 이용해 k번째 퍼즐조각을 이용하는 최소 가격을 전처리한 후, 4진법을 떠올렸다. 주어진 퍼즐판의 모습을 살짝 바꾸면 n-1번째 퍼즐 조각에 0번째 퍼즐 조각을 뺀 모습과 같은데,

이를 1000...000(4) - 1(4) = 333...333(4) 로 생각할 수 있어 0~n-2번째 퍼즐 조각의 가격의 합에 3을 곱하면 된다.

빠르게 구현 후 제출하니 WA... 잉? 코드도 450B 정도로 짧아서 실수할 구석도 없었고 아이디어도 완벽했다. 자료형이나 전처리 형식 등을 바꿔보고, 아이디어를 검증도 해보며 의미 없는 시간과 WA를 차곡차곡 쌓았다. 내가 헤매는 동안 E가 계속 풀리고 1등도 뺏겨서 멘붕이 왔고, 결국 풀지 못하고 ㅌㅌ...

 

 

~1:15

 

다시 스코어보드를 보니 F번이 풀렸고, 마침 풀 문제도 없어서 F를 잡았다. 일단 dp로 접근하는 게 확실한데, 틀을 어떻게 잡아야 할지 도저히 생각이 나지 않았다. LIS를 응용해보고, 그리디스럽게도 풀어보았지만, 예제도 나오지 않았다. 깊이 고민해본 결과, dp1에는 힘의 최댓값, dp2에는 힘의 최솟값을 저장하면 풀 수 있을 것 같았다. 많은 시행착오를 겪고 나서야 예제가 나왔고, 바로 제출하니 AC. 대회 끝나고 친구들의 풀이를 들었는데, 같은 풀이가 하나도 없었고 심지어 정해는 이중에 없었다. 데이터가 약한 건가 싶었지만 대충 아이디어는 다 맞는 것 같아서 더 고민하지 않았다.

 

피카츄 군단

 

~1:40

 

E번이 정말 많이 풀렸고 E를 풀지 못한다면 수상권에 들지 못할 것 같다는 생각이 강하게 들었다. 하지만 디버깅하기 편한 반례를 찾지 못해서 코드를 뚫어져라 보는 것 밖에는 할 게 없었다. 한 10분 정도 쳐다보니 엄청한 실수가 보였는데, 문제는 바로 나머지 연산에 있었다. x와 y를 비교해야 하는 상황에서 x%mod와 y%mod를 비교한 것이었다. 코딩 초반에 수를 줄인답시고 나머지 연산을 아무 데나 때려 박은 나의 실수였다. 그것만 고쳐주니 AC... 어이가 없어 웃음밖에 안 나왔다 ㅋㅋ 이런 류의 실수를 처음으로 해봐서 당황하였지만 좋은 경험이었다.

 

콜롬버스의 달걀

 

~3:00

 

1, 2, 3등이 나란히 5문제를 풀었고, 나는 3등이었다. E번에서 말렸기 때문에 무조건 문제수로 승부를 봐야 했다. 2등이 혼자서 H를 풀었길래 H를 잠깐 봤는데, 가중치 그래프 문제라 바로 포기했다. 참고로 나는 가중치 그래프 문제의 경험이 거의 전무했다. 못 푼 문제를 둘러보니 I번이 가장 만만해 보였고, 구글링을 통해 비슷한 문제를 찾았다. 이 문제를 적당히 응용하면 될 것 같아서 백트래킹을 이용해 빠르게 해결한 뒤 실행시간이 가장 빠른 사람의 코드를 베껴왔다. 이 코드를 이해하는 데에만 30분 정도 걸렸고, 또 I번에 맞게 바꾸는 데에 30분이 걸렸다. 많은 시행착오 끝에 몇 개의 예제를 성공했지만, 특정 테스트 케이스에서 TLE가 나고 말았다. 침착하게 내 코드를 다시 보니 시간복잡도가 말이 안되게 컸다... 통과할리가 없지. '시간복잡도를 줄일 수 있을까?' 3초 고민하고 포기했다.

 

 

~3:30

 

1등과 2등이 모두 C를 해결했지만 나는 C번을 아무리 읽어도 예제조차 이해가 되지 않아 포기했다. 결국 H를 다시 잡았는데, 내가 아는 가중치 그래프가 다익스트라와 플로이드 와샬 알고리즘 밖에 없어서 이들로 풀어보려고 노력했다. 플로이드 와샬은 시간복잡도가 맞지 않아서 버리고, 다익스트라를 쓰기로 했다. 예전에 다익스트라 기초 문제로 풀어보았던 [BOJ] 1753의 코드를 가져와 고민을 했는데, 왠지 k개의 교실 중 하나를 시작점으로 해서 다익스트라를 돌리고, 나머지 k-1개의 교실에 대한 가중치의 최솟값을 구하면 될 것 같았다. 이번에도 검증은 하지 않았고, 디버깅을 하기 싫었기에 천천히 구현을 하여 AC를 받았다. 내가 대회에서 그래프 문제를 해결했다는 사실에 가슴이 조금 벅찼다 ㅋㅋ 2등의 풀이는 MST였는데, 다익스트라와 크게 다르지 않은 것 같았다. (나중에 보니 같을 수가 없다.) 그리고 이 문제의 정해는 무려 BFS+파라메트릭 서치였다.

 

최고의 학교

 

~4:00

 

이젠 할 수 있는 게 별로 없었다. C번을 또 해석하려고 노력했으나 무리였고.. I번을 더 효율적으로 컷팅해봤으나 역시나 시간초과였다. J번은 방향은 보였지만 내 수준에서 해결할 수 없었고, G번은 아무도 안 풀길래 그냥 어려운 줄 알았다. 별 성과 없이 시간은 계속 흘렀고 대회 종료 10분 전부터 줌 화면을 다시 켜야 했는데 키자마자 노트북이 멈췄다. 노트북이 좋았어도 문제를 더 풀지는 못했겠지만 이렇게 대회가 허무하게 끝나버리니 조금은 아쉬웠다.

 

 

~4:30

 

대회가 끝나고 담당 선생님께서 무슨 말씀을 하셨는데 나는 연결 상태가 좋지 않아서 하나도 듣지 못했다. 오히려 줌이 계속 튕겨서 승인을 해주셔야 하는 선생님께 방해가 된 듯하다... 그리고 순위 발표가 이어졌는데, 여전히 계속 화면이 멈추다가 내가 소감을 말할 타이밍에 돌아와서 무사히 소감을 말할 수 있었다. 

 

 

After Contest

 

GCC 단톡방에 Solution PPT가 올라왔고, 다음날에 업솔빙을 시작했다. 해설을 쭉 보니 문제가 난이도 순서였던 것 같은데 분명 문제가 난이도 순으로 배치되지 않았다는 공지가 올라왔었다... 사실 이게 노린건지 궁금한데, 물어보지는 않았다.

 

C번은 dp가 아니라 단순 수학문제였는데, 이해만 완벽하게 한다면 나쁘지 않게 풀리는 문제였다. 적당히 합동식을 세우고 케이스를 나눠서 풀면 된다. C번을 정확히 이해하지 못한 점이 가장 아쉬웠다. 예제에 대한 간단한 해설이라도 있었으면 좋았을 것 같다. (문제 해석하는 것도 실력이긴 하다.)

 

코드 배치하기

 

G번은 좌표 정렬 후 스위핑을 하면 풀리는 문제였다! 충분히 풀 만한 문제인데, 다른 참가자가 시도도 안 한다는 걸로 문제가 어렵다고 판단해버린게 많이 후회스러웠다. 시간 분배를 잘 했더라면... 하는 아쉬움이 생긴다.

 

한강 뷰 아파트

 

I번은 사실 올솔 방지용 문제였다 ㅋㅋ RNA의 상태를 정점이 A, U, C, G인 그래프로 표현하고 케이스 워크 해주면 된다. 설명은 간단해 보이지만 이 풀이에 도달하는 과정이 쉽지 않고, 생각해줘야 하는 상황이 많아서 솔루션을 이해하기도 힘들었다.

 

이상한 효소

 

J번은 이해를 포기했다. 각 칸마다 만나는 직원 수를 구해놓고, 계속 갱신하면 된다고 하는데 구현 못할 것 같다.

 

민방위 훈련

 

여름방학에 진행한 대회에서는 1학년 7등으로 수상권은 커녕 상장도 못 받았었는데 6개월이 지난 지금 나름 설욕전에 성공한 것 같아 뿌듯했다...ㅎㅎ 긴 글을 쓰면서 다시 대회를 하는 듯한 기분을 받을 수 있었고, 올해 또는 내년에 있을 7회 GCC를 빨리 준비하고 싶다는 생각이 들었다.