2023년도 PS 회고록

작년 한 해는 많이 놀았던 것 같습니다. 군대에서 전역을 하고 6개월 동안 집에서 계속 PS를 하고, 교회 신앙생활이랑 요리도 배우고 좀 쉬어가는 느낌이었습니다. (물론 2년간 뺑이친 걸 생각하면 좀 더 놀고 싶어서 한 학기 더 휴학할 예정이긴 하지만요.) 그러다보니 올해는 PS 관련된 활동을 많이 했었기도 했고 PS가 많은 영향을 끼쳤던 것 같습니다. 이번 글에서는 이에 대해서 회고를 해보고자 합니다.

 

PS는 제가 군 생활을 하면서 후임 덕분에 시작했었는데요. 당시에는 그냥 '사무실 근무시간 녹이기 위해서 해볼까? 코테도 준비할겸 같이하지 뭐' 이런 생각으로 PS를 시작했던 것 같습니다. 저는 군대가기 전에는 학부연구생으로 2년 동안 AI만 공부했었는지라 PS에 대해서는 하나도 몰랐었습니다. 그리고 'PS는 걍 코테 뚫을려고 하는거 아닌가? 이게 도움이 될까?'라는 생각과 같이 PS를 열심히 하는 것에 대해서는 좀 시간낭비라는 생각이 들었습니다. 그래서 좀 하다가 말고 / 하다가 말고 이런 생활이 반복되었습니다.

 

PS에 대해서 제가 깊게 파기 시작한 건 제작년 11월 쯤부터 그랬던 것 같습니다. 정확하게 어떤 계기로 그때부터 열심히 하게 된 건지는 기억이 잘 안 나는데, 아마 코드포스를 처음 보고나서부터 CP에 대한 관심도 생기고 PS를 열심히 시작했던것 같습니다. 그러면서 자연스레 실랜디도 되고, 골랜디도 어느정도는 되기 시작하고... 하다가 작년 6월에 전역하게 되었습니다. 전역을 한 후에는 대회들도 참가해서 팀으로도 같이 대회를 출전해보기도 하고, 백준에서 대회 출제자 및 운영자로 들어가서 아레나도 운영해보는 등 여러 PS 관련 활동들을 할 수 있었습니다. 제가 올해 PS 관련 활동들은 아래와 같이 정리할 수 있습니다.

 

1. 현대 모비스 알고리즘 대회 - 예선 광탈

2. UCPC 대회 - 본선 진출, 44팀 중에서 24등으로 마무리. 

3. 삼성 DX 알고리즘 하계 특강 - 수료 및 Pro 검정(B형) 취득함.

4. 제 2회 보라매컵 - 예선 및 본선의 출제자로 참여, 총 4 문제 출제.

5. Meta Hacker Cup - Round 2에서 1,540등으로 마무리. 기념 티셔츠 획득.

6. Codeforce - 블루 달성.

7. BOJ & solved.ac - 다이아 달성.

8. Softeer HSAT 8차 자격인증 - 취득함.

 

그 중에서 기억이 많이 남는 활동은 UCPC 대회 참여, 삼성 알고리즘 특강 및 제 2회 보라매컵 출제한 것이었는데, 이에 대해서 좀 더 자세히 이야기하고 글을 마칠려 합니다.

 

1. UCPC 대회

제 첫 팀 대회이자, 오프라인 PS 대회였습니다. 당시에 제가 코드포스 블루도 한 번 찍었던걸로 기억해서 CP는 어느정도 익숙하다고 생각했으나 팀 대회는 매우 달랐습니다. 특히나 본선 진출이 확정되고나서 당일치기로 서울에 올라가 팀원들과 같이 팀 연습을 하는 경험도 색달랐고, 실제 대회에서 대략 5시간 동안 계속 문제보고 팀원이랑 서로 이야기하면서 아이디어 공유하는 경험도 재밌었습니다. 이외에도 예선때 팀원들이 부대 내에 있는 상황이라 디스코드 채팅으로만 서로 이야기하면서 푼 것도 신기했습니다. 이 뒷북 글을 보게 될지는 모르겠지만 테라포밍UCPC 팀원분들 모두 고생했고 언제 서울에서 테라포밍마스 한 판 해요! (전역하고 이 게임이 이렇게 그리울줄은 몰랐네요 ㅠㅠ) 다시 한 번 팀으로 올해 UCPC 참여해도 좋구요 :)

 

2. 삼성 DX 알고리즘 하계 특강

SWExpertAcademy의 문제들 특징상 구현이 매우 중요해서 구현을 매우 연습할 수 있던 기간이었습니다. 이외에도 교수님의 특강도 재밌었고, 삼전 건물에 들어가서 시험도 치는 것도 색달랐습니다.(그리고 화장실 디자인이 매우 예쁘다고 들었는데, 실제로 디자인이 예쁘더라구요 ㅎㄷㄷ)  그것말고도 이 특강을 하면서 O(logN) LCA 및 Lazy Segment Tree 구현도 익힐 수 있었습니다. 

 

3. 제 2회 보라매컵

문제를 출제하는 건 매우 색다른 경험이었습니다. 항상 문제를 풀기만 하던 입장에서 출제를 처음해보았는데, 문제를 하나 출제하기까지 이렇게 여러 단계들이 있는지는 처음 알았습니다. 난생 처음보는 testlib.h도 다뤄서 generator도 만들어보고, edge 케이스 관련해서 직접 테케도 만들어보고, 문제 아이디어를 가지고 이에 알맞는 지문을 작성하고, 다른 출제진의 문제도 검수해서 피드백도 주고... 이렇게 많은 과정을 거쳐야 문제가 나오는줄은 몰랐습니다. 처음 출제하는 입장에서 저는 처음에는 약간 헤매었지만 다행이 운영진 및 검수진 분들의 도움을 받아서 성공적으로 문제를 출제할 수 있었습니다. (특히나 지문 부분에서 처음에 제가 작성한 것보다 훨씬 나아지는 마법을 보았습니다.) 4 문제를 준비하느라 나름 힘들었었고 대회랑 오픈 컨테스트(특히나 아레나 였던 본선)에서 제발 문제가 없기를 마음 졸이면서 맘고생도 했었지만, 끝나고 나니 문제를 출제해보았다는 사실에 매우 뿌듯했습니다. 그리고 다들 꽤 좋은 평가를 주어 한동안 문제 기여창만 계속 보면서 행복했었습니다. 이것도 한참 뒷북이라 볼지는 모르겠지만 운영진 및 검수진 분들 매우 고생하셨습니다!

 

이제 마지막으로 제가 출제한 문제들을 소개하면서 글을 마치도록 하겠습니다. 각각마다 TMI도 같이 달아둘게요 :)

• BOJ 29695 기지방호 - G1
  • 예선 C번 문제.
  • 이 문제는 아주 예전부터 구상해왔던 문제긴합니다. 다만, 당시에 생각했을 때는 TSP DP로 푸는 문제였어서 반려당했습니다. 그래서 해당 문제의 컨셉을 지키면서 어떻게 다르게 낼 수 있을까 생각하며 산책하다가 우연히 '플로이드-워셜을 이렇게 꼬아본다면?'이라는 생각을 하게되어 출제하게 되었습니다.
  • 제가 적은 정해와 다르게 DP 부분을 O(min(F^3T, F^4)) 부분을 O(F^3logT)로도 푸신분들도 있었습니다. 또한, 전술간의 전환을 cost 1씩 증가하는 것으로 생각해서 2D cost에서 다익스트라로 푸는 별해도 있었습니다.

 

• BOJ 30205 전역 임무 - S2
  • 본선 B번 문제.

  • 

    이 게임을 모티브로 출제했습니다.

  • 기억은 안 나지만 어느 스트리머가 'Yeah! You Want "Those Games," Right? So Here You Go! Now, Let's See You Clear Them!'에서 해당 게임을 너무 못해 속이 타서 최적해를 떠올리다가 문제로 내도 괜찮겠다는 생각이 들어 출제했습니다. 
  • 저랑 운영진들의 예상과는 다르게 대회중에 많은 분들이 고전했던 문제였습니다. 이 글을 보신분들 중에 혹여나 이 문제로 고통받으신 분들이 있다면 죄송합니다... (이 문제 때문에 배경을 못 받은 분들도 계셔서 마음이 아팠습니다 ㅠㅠ)

 

• BOJ 30206 차량 배치 - G4
  • 본선 C번 문제.
  • 이 문제는 LCA 관련 문제를 생각하다가 떠올린 문제였는데, BFS + 조합론은 많이 생소할 것 같아서 출제했습니다. 특히나 보라매컵에서 한 번도 조합론 문제가 나온적은 없어서 이렇게 스타트를 끊어보고도 싶었습니다.
  • 출제하는 것도 나머지 3문제 보다 비교적 훨씬 쉬었어서 편했던 문제였습니다. 그리고 문제 아이디어도 제 마음에 들었던 문제였는데, 꽤 좋은 평가를 받아서 매우 기뻤습니다.

 

• BOJ 30210 BX 내기 - P3
  • 본선 G번 문제.
  • XOR Trie를 좀 더 generalize하면 이렇게도 출제할 수 있지 않을까 생각해서 출제한 문제입니다. 이 문제를 통해서 보라매컵 참가자분들에게도 XOR Trie를 소개할 수 있으면 좋겠다라는 생각도 있었습니다.
  • 출제가 확정되고 나중에 들은건데, 실제 대회에서는 인터넷 사용이 금지되었다고 합니다. 그래서 Trie가 Segment Tree처럼 대회 참가자들에게는 잘 알려진 자료구조가 아니라 판단되어 Trie만 가능했으면(Trie 모르면 못 푸니깐) 출제할 수 없었는데, 다행이 다른 Maximal XOR 문제처럼 이 문제도 이분탐색을 활용해서 풀 수 있어 출제할 수 있었습니다.
  • 이 자리를 빌어 실제로 저런 게임을 한 적도 없고, 하더라도 바보게임만 4시간 동안 돌렸지 후임들에게 계산하라고 시킨적은 한 번도 없음을 밝힙니다. 부조리는 근절되어야 합니다 :)

 

긴 글 읽어주셔서 감사합니다. 올해도 다들 즐거운 PS 생활하세요 :)