2025 ACPC 참가 후기

ACPC 포스터

 

---

 

가서 뭘 했냐..? 충남대학교에서는 누가 나갔는지, 나간 사람 성적은 어떤지.. 궁금해 하실 분들도 있을 것이라고 생각한다.

 

충남대학교에서 더 출전한 사람중에 아는 사람은 없다. 있을 수도 있지만, 뇌피셜로 충남대학교에서 출전 한 사람은 나 혼자다.

 

교통비를 당일 현금 지급받아서, 교통비로 돈을 받았으면 받았지, 더 지출이 나가거나 그러지는 않았다.

 

그날 하루의 일과를 시간대 별로 정리해 보았다.

---

- 기상

6:50 분에 일어났다. 가볍게 캔커피 한잔하고, 창문 열고 환기 좀 했다. 멀쩡한 정신상태와, 깨끗한 정신상태를 최대한 유지하려고 했던 것 같다. 전날에 과제와 밀린 일을 하다가, 00시에 자서 그런지 머리가 좀 어지러웠던 것 같다.

 

찬 바람을 맞고, 일부러 찬물로 샤워 했다. 군대에서 했던 각성요법을 내가 인생 사는데 다시 하는 순간이 올 줄 몰랐다.

 

그후 간단하게, 샌드위치랑, 빵, 생과일 음료수를 마시고, 생각보다 늦어서, 택시를 타고, 샘머리 고속 버스 정류장으로 달려갔다...

 - 이동 (대전 샘머리 > 서울 경부 > 센터필드)

대전 샘머리 고속버스 터미널에서, 서울 경부까지 버스를 타고 이동했고, 2시간 정도 걸렸다. 원래 수원역까지 SRT를 타고 가려고 했지만, 이미 다 매진이여서 어쩔 수가 없었다.

버스에서는 노션에 정리해 둔 알고리즘들을 복기했고, 중요한 알고리즘들은 내 뇌속, CPU 캐시에 올려놓았다.

 

한 30분 정도 그랬고, 사실 졸다가 일어났더니 서울 경부 고속 버스 터미널에 도착했다... >.<

 

후에, 바로 터미널에 있는 김밥천국 집에서, 김밥으로 끼니를 때웠고, 혹시 늦으면 대형사고여서, 여유롭게 버스타고 센터필드로 향했다.

 

센터필드...

확실히, 지방에 살다보니, 서울에 올때마다, 높은 건물들을 보면 적응이 안된다... 나는 참고로, 센터필드 1, 2층 카페가 있는 쪽을 돌아다니면서, office층으로 어떻게 올라가는지 찾고 있었다... 에궁..

 

바로 보이는 AWS 전경..

찍은 사진은 더 이상 없다. 안에 임직원 분들도 계시고... 그냥 가서 사진 찍으면 민폐가 될 까봐... 안찍었다...

황현석 41번 참가자 오징어 게임에 온걸 환영한다...

 

가서, 바로, 이름표랑, ACPC 티셔츠를 받았다.. 티셔츠를 바로 갈아입으라고 하셔서.. 화장실 가서 갈아입었다.

 

그리고 뭐 좀 대기타다가, 대회를 쳤다. 아는 사람드 한명도 없고... 충남대에서 일단 나혼자 온걸로 알고 있었으니...

 

---

오랜만에 알고리즘 문제를 풀었다. 최근 개발공부를 하고, 다양한 기술을 먼저 익히려고 하다보니, 알고리즘을 정말 공부할 시간도, 풀 시간도 없었다.

 

내가 오랜만에 알고리즘 문제, 그것도 고인물들 대회급 문제를 내가 잘 풀 수 있을까에 대한 고민이 있었다... 

 

이런 고인물 대회는 오프라인 대회로 처음 나가보았다. 대회 시작하자마자, 울리는 페이지 넘기는 소리, 동시에 들리는 수백 수천가지의 타이핑소리는 나를 진짜 정신 나가게했다...

 

나는 첫 문제를 읽고 있는데, 무슨 벌써 타이핑을 하는 사람이 있다고..? 허허..

 

문제는 안정화 2 문제인데, 나는, 서면으로 인쇄 된 안정화 문제를 풀고있었다... 진짜 개멍청멍청...인쇄 된 안정화 문제는 N=200000, 이어서, 그걸 최적화 할 생각을 하고 있었다...

 

그러다가 합리적인 생각을 하게 되었다... 어? 다들 타이핑을 하는거 보면, 쉽게 풀리는 문제다..> 근데 지금 내가 읽고있는건 진짜 절때 바로 나올 수 없는 수준의 그리디 문제이다 > 문제가 틀리다

 

그제서야, 화면을 들여다 봤고, 문제의 제한이 달랐다.. N=2000 이었고, 브루트포스 알고리즘을 사용 하는 아이디어가 바로 떠올랐다... >.<

 

그 다음 C 솔브는, 살짝 느리다...동전이 부족해 문제는, 풀이는 금방 나왔다. 하지만, 그 풀이는 내 머릿속에 처음에 바로 폐기 되었다.

 

내 풀이는 $O(NMlogM)$ 이었는데, 이거 1.3억이었다..N=300, M=30000 이었고, 계산기가 금지라, 대충 어림잡아, 2~3억으로 계산했었다..

 

바로 폐기 했고, 돌고 돌아.. 너무 답이 없어보여서, 해당 문제를 파라매트릭 결정 문제로 치환하여 풀었다... 근데 바로 풀려서 어이가 없었다.. ㅡㅡ

 

B번 문제는 바로 읽고 넘어갔던 문제인데.. C를 풀고 다시 풀이를 시작했다. 우선순위로 구현 할 수 있을 것 같았는데, 나는 그냥 쉬원하게 세그먼트 트리를 넣어서 풀었다.

 

우선순위를 써도 풀리는지는 모르겠는데, 내 풀이는 일단 세그먼트 트리를 쓰면 풀리니까, 바로 구현했다. 풀이부터 구현까지 23분정도 걸렸고, 무난무난하게 풀었던 것 같다..

 

다음은... 그냥 내 모든 시간을 부어버린.. 트리 게임 문제였다...

이걸 언급해도 되는지는 잘 모르겠는데,  일단 들어간 알고리즘은, Tree + DynamicProgramming on Tree + Smaller to Large + Trie + Lazy Propagate on Trie + Greedy + UnionFind 정도가 들어갔다.

 

진짜 그냥 괴랄한 구현문제였고, 고인물들은 딸깍수준 이었다고 한다.

 

Trie에 Lazy를 적용하는 것은 나로써는 큰 도전이자 모험이었다. 하지만 이진 배열 Trie 구조였고, 세그먼트 트리에서 그렇게 많이 해본 Lazy적용이라 별로 힘들지는 않았다.

단지, 처음 시도해보는 트라이에서의 전파지연 구조라, 잘 돌아갈지 걱정만 계속 했던 것 같다...

 

나도 딸깍 수준으로 끝날 줄 알았으나.. 맞왜틀 지옥에 빠졌다. 결국에는 울며 겨자먹기로, 코드 리펙토링을 시작했고, 내가 어느 부분에서 로직을 바꾼지는 모르겠지만, 코드가 갑자기 통과했다.

 

코드가 통과한 시각은.. 대회 시작 후 3:43분이다.. 남은 시간동안, 표절 피하기를 풀었고.. 풀면서 속으로 욕을 너무 했다...

 

"아.. 이거 아호코라식으로 무언가를 하는거다... 아호코라식 자체를 까먹었다..."

 

그래도 43등 해서 만족한다. 고인물들 대회에 나가 43등이나 하다니.. 이런...

 

끝나고 사진 찍었는데, 사람들 뒤에 숨어가지고 나는 진짜 안나왔을 것이다.. 

아.. 맞다.. 대회 시작전에 인터뷰를 하게 되었는데...

 

참가 동기랑, 대회 예상 순위나, 각오등을 물어봤던 것 같다.. 진짜... 참가 동기.. 없음... 대회 예상 순위... 반타작.. 각오.. 1등하겠다...? 를 말했다..

 

영상으로 나오면 나는 이제 잠못자고 이불킥 겁나 쌔릴 것 같다... ㅜ

 

---

 

ACPC 재미있었고, 대회 통제 해주신 AWS 임직원 분들 모두 고생 많으셨습니다. 문제 난이도 커브 괜찮았고, 문제 자체가 도전을 일으키는 문제여서 좋았습니다.