2026 ACPC 후기

 

안녕하세요. 올해 7월 말 COEIC 예선을 치르고, 8월 2일에는 2026 ACPC 본선을 다녀왔습니다.

 

ACPC는 개인적으로 예선부터 꽤 좋아하는 대회입니다. COEIC과 같이 여러 번 시도할 수 있는 예선 시스템이 있고, 참가자의 현재 상태를 잘은 못해도 얼추 분석하는 시스템이 좋은 것 같습니다.

COEIC 예선에서 좋았던 점

COEIC 예선, 907점

 

이번 예선에서는 41위를 했습니다. 다만 중간에 30분 정도 종이에만 생각을 적고 컴퓨터를 한 번도 만지지 않았는데, 노트북이 절전 모드로 들어가면서 부정행위로 퇴장 처리되었습니다. 허허허.

 

문제는 이제 자세히 기억나지 않지만, Mo's offline query 최적화와 조금 까다로운 쿼리 처리 문제들이 있었습니다. 플래티넘 문제까지는 관찰 하나를 잘 잡아서, 처음에는 복잡해 보이던 쿼리를 조금 더 단순한 형태로 바꾸는 문제가 많았습니다.

 

제가 좋아하는 대회의 감각

COEIC

짧은 시간에 기발한 한 방을 떠올리는 문제보다, 비교적 평이한 문제를 오래 붙들고 제출 횟수와 풀이 시간을 같이 관리하는 쪽이 저에게는 더 맞았습니다. 다른 대회가 틀렸다는 이야기는 아니고, 이쪽이 문제를 푸는 과정 자체를 더 남겨 주는 느낌이었습니다.

대신 생각보다 오래 걸린다

3h+

스트레스가 덜하다고 해서 가벼운 예선은 아니었습니다. 저도 제대로 치르면 3시간이 넘게 걸렸고, 이번에는 중간에 봐야 할 일이 있어서 끊고 나왔습니다.

8월 2일, ACPC 본선

저는 어김없이 7시에 일어나서 9시에 유성복합터미널로 갔습니다. 유성복합터미널은 진짜 좋았습니다. 1년 전에는 샘머리공원에서 서울 센트럴로 갔던 기억이 있는데, 이제는 집 앞 유성에서 바로 갈 수 있게 되었습니다.

 

서울 센트럴에서 간단히 김밥을 먹고, 12시에 ACPC 대회장에 도착했습니다.

 

테헤란로 쪽 센터필드 EAST

 

여기도 어느덧 3~4번은 와 본 것 같습니다. AWS 교육을 들으러 오기도 했고, ACPC로만 벌써 두 번째입니다.

 

센터필드 EAST 18층 로비

 

아마존 AWS를 떠올리게 하는 장식이 있었습니다. 오랜만에 보니 반갑기도 했습니다. 그리고 이번 대회는 총 10문제였는데, 1등이 6솔인 파멸적 문제 세트였습니다. 

대회를 진행하면서 스코어보드를 지속적으로 확인 했는데, 대회 시작 1시간째 부터 4솔브로 도배가 되더니, 끝날 때 까지 4솔이 거의 대부분 이었습니다.

 

https://www.codetree.ai/ko/frequent-problems

 

문제는 위 사이트에서 공개되어 있습니다. 저는 5문제에서 AC를 받았지만, 그중 하나는 데이터가 부족해서 통과한 것이었습니다.

1. 큐브 위 도미노 · Silver 1

이 문제를 보자마자 꽤 스트레스를 받았습니다. 관찰을 통해 수식을 유도하는 문제인데, 특히 현실의 3차원 공간에서 굴리고 돌려 보는 류는 제 머릿속에서 바로 정리되지 않는 편입니다.

 

일단, 이런 류의 문제는 한번 생각이 뒤틀리면, 답이 안나오는 문제류라고 생각해서, 나중에 풀기로 했습니다. 나중에 10분정도 고민하고, 수식을 유도해서 코드를 작성했습니다.

 

long long 을 사용하지 않아서 4번틀렸습니다. ^^

 

2. 로봇의 이동 · Gold 5

 

이 문제는 기본적으로 3차원 BFS 탐색 문제였습니다. 다만 빙판처럼 한 번 이동을 시작하면 다음 벽에 부딪힐 때까지 계속 진행해야 한다는 조건이 있었습니다.

 

1

다음 칸이 아니라, 멈추는 칸을 본다

한 칸씩 이동시키는 시뮬레이션으로 생각하면 상태가 애매해집니다. 방향을 골랐을 때 실제로 도착하는 위치를 하나의 전이로 만들었습니다.

2

방문 상태에 방향을 남긴다

같은 위치라도 어떤 방향에서 들어왔는지에 따라 다음 선택이 달라질 수 있어서, 3차원 visited 배열에 방향까지 기록했습니다. 문제를 평면 BFS처럼 읽으면 빠뜨리기 쉬운 부분이었습니다.

3. 독립 전력망 · Gold 1

이 문제에 40분을 썼습니다. 풀이와 구현은 10분 안에 끝났는데, int 함수에서 반환값을 쓰지 않았습니다. 컴파일은 되었고 코드는 돌았지만, 반환값이 필요한 경로에서 함수 끝에 도달하면 C++에서는 정의되지 않은 동작이 됩니다. 어디서 어떻게 터질지 일정하지 않으니, 런타임 에러만 보고 원인을 찾기가 곤란했습니다.

대회에서 다시 배운 기본

풀이가 맞아 보일 때일수록 자료형, 반환값, 초기화처럼 너무 기본적인 부분을 먼저 확인해야 했습니다. 이번에는 디버깅을 포기하고 함수를 처음부터 다시 썼고, 반환형을 void로 바꾸자 얼떨결에 통과했습니다.

4. 고속도로 배송 · Platinum 5

개인적으로 이 문제는 직관을 강하게 요구하는 문제였습니다. 상태를 무엇으로 잡을지, 그리고 상태를 조금 거칠게 관리해도 한 전이 라운드에서 최대 O(N)개로 제한된다는 것을 직관적으로 느꼇습니다.

 

여기서 중요한 것은 처음부터 가장 빠른 자료구조를 고르는 일이 아니었습니다. 상태 수가 정말 그 정도로 묶인다는 확신이 생기고 나서야 map으로도 일단 굴려 볼 수 있었습니다. 저는 시간 초과와 메모리 부족이 같이 나서, 이전 라운드와 다음 라운드의 map을 swap하는 방식으로 바꿨습니다. 이후 pair로 들고 있던 키도 long long으로 인덱싱해서 unordered_map에 넣었고, 그제야 통과했습니다.

 

지금 다시 보면 자료구조 최적화 자체보다, “이 상태들은 다음 라운드로 넘길 것만 남기면 된다”는 판단이 먼저였던 것 같습니다. 그 판단이 없었으면 map을 바꾸는 것만으로는 계속 불안했을 것 같습니다.

 

5. 와일드카드 매칭 · Diamond 1

저는 이 문제를 뚫었고, 결국 오답이었습니다. *를 기준으로 문자열을 나누고, 각 조각을 앞에서부터 빠르게 KMP를 사용해서 맞추자는 그리디한 방향으로 갔습니다. 

 

하지만, 간과한 실수는 KMP로는 '?' 문자열을 해결 할 수 없었습니다. 간단하게 요약하자면, 저는 제가 미쳐 생각하지 못했던 반례들이 많았고, 일부 평이한 케이스들만 모두 통과하는 실패함수를 만들었습니다. 실제로는 한 조각의 접두사·접미사 정보와 전체 패턴의 선택지가 같은 상태가 아니었습니다.

 

그래도 최대한 많은 경우를 커버하려고 실패 함수를 여러 번 만졌고, 결과적으로 약한 데이터는 뚫어 버렸습니다.

 

네... O.o

11등

11등?

 

막상 AC가 떴을 때는 잘했다고 생각했습니다. 그런데 나중에 보니 데이터 부족이었습니다. 순위표에는 11등으로 남았지만, 아닌건 아니긴 합니다.

 

이번 대회 기록은 미래에 CP를 더 잘하게 된 황현석 군에게 바치겠습니다. 언젠가는 제대로 맞힌 풀이로 여기까지 올라올 수 있길.

GG