제2회 한국항공대학교 프로그래밍 경진대회(KAUPC) 개최 후기

참조: 제1회 한국항공대학교 프로그래밍 경진대회 개최글

https://suhwanc.tistory.com/186

2021 Kaupc 한국항공대학교 프로그래밍 경진대회 개최 후기

문제 확인하기
https://www.acmicpc.net/category/detail/3184

제2회 한국항공대학교 프로그래밍 경진대회(KAUPC)

 

9월 17일 제2회 한국항공대학교 프로그래밍 경진대회(KAUPC)를 개최하였습니다.
2021 KAUPC 글에서 3번 내용부터 적어보겠습니다.

1. 문제 출제 준비

---

1) 참가자의 실력

출제진들 사이에서도 이야기가 많았던 내용입니다. 대회를 개최한다면 가장 잘하는 사람이 어느 난이도의 문제까지 맞출 수 있을까에 따라 최고 난이도 문제의 난이도 조절을 해야 하는데, 잘하는 사람들이 어느 수준의 문제를 대회에서 풀 수 있을지 생각하는게 어려웠습니다. 왜냐하면 교내에서 잘하는 분들이 참여 여부 미지수, 최근 알고리즘 문제를 풀지 않음, 실제 대회에선 어느정도 퍼포먼스가 나올지 모르겠음 등등 다들 하나씩 고려해야 할 상황이 었었습니다.
그래도 잘하는 팀이 최소 3팀은 나올 수 있을 것 같으니 출제진의 목표는 문제의 개수가 총 9개니까 골드 상위 ~ 플래티넘 하위 문제를 여러 개 만들어서 변별력을 높히는 방향으로 정했습니다.

---

2) 알고리즘 종류

최대한 다양한 유형의 알고리즘을 내는 것을 목표로 하였습니다.

1. 단순 구현
2. 트리에 대한 이해
3. 백트래킹
4. 이진 탐색
5. 시뮬레이션
6. DP
7. 누적합
8. BFS + 비트마스킹
9. 브루트포스 + 누적합 + DP

처음 문제 출제 준비를 했을 때만 하더라도 너도 나도 시뮬레이션, BFS 문제를 만드려고 했던게 기억나는데, 다행히 결과적으로는 다양한 유형의 문제가 나올 수 있게 된 것 같습니다.

저는 올해 1학기에 들었던 추천시스템 수업 이론에 대한 간략한 설명을 주고, 구현하는 시뮬레이션 문제 지문을 작성했는데, 문제 채택 과정에서도 지문이 난해하다는 평가를 받아 이게 채택됐다면 정말 큰일이 났을 것 같습니다.
저도 BFS 문제도 만들어볼까 생각은 했었지만, 주변 친구들이 제가 BFS 문제를 좋아하는 것을 알고 있어서 문제를 만들지 않았고, 대신 재밌는 지문의 DP와 누적합 문제를 만들었습니다.

* 필수로 들어가면 좋은 문제들

• Triathlon과 같이 모든 팀이 1문제는 풀 수 있도록 하는 문제
• 알고리즘 대회 준비자가 아닌 코딩테스트만 준비하는 사람들도 풀 수 있는 문제
• 시뮬레이션 문제는 최대 1문제
• 프로그래밍 대회이니만큼 이름에 맞게 생각을 많이 해봐야 풀 수 있는 문제

---

3) 목표 난이도

문제 목표 난이도는 문제를 교체하면서 조금씩 올라갔습니다.
원래는 제가 4문제를 만들 예정이었으나, 문제 만드는게 재밌어야 하는데 문제는 처음 만들어보고, Polygon도 처음 사용해보고 너무 힘들어서 1문제는 내부 검수까지하고 제외했습니다.

문제 예상 난이도 (총 9문제)

• 브론즈 1문제
• 실버 2문제
• 골드 쉬움~중간 난이도 2문제
• 골드 중간~어려움 난이도 2문제 ~ 3문제
• 플래티넘 1문제 ~ 2문제

출제 문제는 일단 출제진들이 만들고 싶은 문제들을 먼저 스프레드시트에 올리고, 회의를 진행하여 채택을 하는 형식으로 진행하였습니다. 하지만 이 방법은 출제진의 수가 많으면 좋은 문제들이 나올 수 있겠지만, 출제진의 수가 적기 때문에 먼저 스프레드시트에 문제를 다 적은 사람이 있으면, 나중에 스프레드시트에 문제를 적는 사람들은 그동안 적힌 문제 유형들을 보고 새로운 유형의 문제를 위주로 만들 수 밖에 없어서 개인적으로는 좋은 방법은 아니였던 것 같습니다.

기간은 한 달은 문제 선정, 한 달은 문제 수정 / 교체 및 Polygon 문제 제작, 나머지 기간은 BOJ Stack으로 이동하고 검수를 진행헀네요.
회의를 매우 많이 진행하면서 문제를 완성하고, 검수하기 전에 "설마 이렇게 문제를 최대한 열심히 만들었는데 검수할 내용이 있을까?"했는데.. 고칠 부분이 매우 많습니다...
특히 검수진 분들이 검수를 엄청 열심히 해주셔서 좋은 지문이 나왔던 것 같습니다.

그리고 내년 대회는 문제 출제한 사람들이 많아졌기 때문에 그래도 올해보다는 문제 출제 기간이 짧아지지 않을까 생각합니다.
그런데 그때되면 저 빼고 전부 직장인이라 가능할지는 모르겠네요.

---

4) 대회 결과

대회 신청팀은 25팀(75명)이였지만, 실제 참여팀은 총 24팀(72명)으로 작년과 매우 비슷한 인원이 신청하였습니다.

대회 결과는 정말 다행히도 최악의 상황은 면했다고 말할 수 있습니다.

Open Contest에서는 모든 문제가 풀렸습니다. 하지만 교내 대회에서는 참여한 모든 팀이 A번 문제를 풀 수 있었지만, 모든 문제가 풀리지는 않아서 좋은 대회는 아니였습니다. 특히 1위팀이 G번 문제를 풀지 않았다면 1위가 누가 먼저 4문제를 먼저 푸느냐로 변질될 뻔 했네요. 대회 진행하다가 이야기를 들었는데 그런 대회가 되었다면 망한 대회라고 합니다. 그건 피해서 정말 다행입니다.

---

 

2. 문제 출제 후기

---

1) Triathlon

원래 스트릿 코딩 파이터 2라는 제목으로 비대면 → 대면으로 문제 소재만 바꾸고 편하게 지문을 만드려고 했던 문제입니다.
근데 지문을 완성해보고나니 양심을 지하철 분실물 센터에 두고 온 수준이라 Triathlon으로 문제를 전면 교체했습니다.
문제 소재는 문제 지문을 만들기 며칠전에 친구들이 마라톤을 나간다고 하길래 철인 3종 경기가 생각나서 알고리즘 철인 3종 경기라는 컨셉으로 문제 지문을 제작하게 되었고, 여기에 나오는 문제 유형은 제가 작년 여름방학동안 폐관수련 했었던 그리디 알고리즘과 다이나믹 프로그래밍 문제, 그리고 풀이를 찾아봐도 이해하기가 어려웠던 애드혹 문제가 개인적으로 매우 어려운 유형이라고 생각하기 때문에 알고리즘 철인 3종 경기 유형으로 정했습니다.

---

2) 입맛이 까다로운 코알라가 유칼립투스 잎을 행복하게 먹을 수 있는 방법

문제 지문은 Koala에서 문제를 출제하고 있는데 Koala에 대한 내용이 없어서 학회와 관련된 문제를 만들자고 생각했습니다. 코알라가 유칼립투스 잎을 먹는다는건 여름방학때 처음 알았는데, 학회 아침 기상 인증 노션 페이지 제목이 `아침에 일어나는 코알라가 유칼립투스 잎을 먹는다`라는 내용이였습니다. 그래서 이걸 토대로 유칼립투스 잎에 대한 내용을 검색해서 문제 지문을 완성했네요.
제가 생각한 이 문제 티어는 골드 3이였습니다. 코알라가 3가지 행동중에 하나를 하기 때문에 점화식만 생각해 보면 골드 중하위 문제 점화식과 비슷한 내용이라 골드3보다 티어가 높게 잡히지는 않겠지 생각했지만, 대중적인 냅색 풀이가 있었고 골드1이 되버렸네요.

---

3) 장마

문제를 만들 초창기엔 풀이를 잘못 생각하여 제외하려고 했던 문제였는데, gojib2002님이 풀이를 살려서 채택된 문제입니다.

지문도 검수진 분들 덕분에 직관적으로 이해하기 쉬운 지문이 나와서 이 문제도 장난감 섞기와 비슷하게 사용하는 알고리즘 유형 티어 자체는 실버로 낮은 편이지만, 해당 누적합이 어떤 의미를 가지고 있는지 꾸준히 생각하면서 풀어야 했기 때문에 대회 성격에 맞게 좋은 문제가 나왔다고 생각합니다.

이 문제는 예제를 이해할 수 있다면 누적합이라는 유형은 바로 찾을 수 있도록 만들어졌습니다. 하지만 여러 개의 누적합을 한 번에 적용하는 기법을 찾아야 시간초과를 면할 수 있는 함정이 존재했기 때문에 진짜 많아봤자 1팀~2팀만 풀 수 있을 것이라고 생각했습니다. 대회 직전까지 문제가 안풀려서 아무도 못푸나 싶었는데, 대회 끝나기 직전에 한 팀이 풀 수 있었네요.

여러 개의 누적합을 한 번에 적용하는 문제는 아래 문제를 참고하시길 바랍니다.
https://www.acmicpc.net/problem/19951

19951번: 태상이의 훈련소 생활

---

 

3. 제가 풀은 나머지 문제들 풀이

---

1) 자바의 형변환

제가 생각한 풀이의 경우엔 일반적인 트리처럼 부모 노드에 자식 노드를 저장하는 것이 아니라, 자식 노드에 부모 노드를 저장하는 방법입니다.
이러면 A노드의 부모노드가 B노드인지, B노드의 부모노드가 A노드인지 확인하는 것은 딱 두 번의 while문 만을 사용하여 코드를 간단하게 작성하여 문제를 풀 수 있습니다.
하지만 교내 대회 제출한 분들의 통과 코드를 보니까 코드를 너무 길게 작성하고 통과해서 쉽게 풀고 넘어갈거란 예측이 빗나갔었네요.

---

2) 캔 주기

입력값이 매우 작습니다.
입력값이 매우 작다 = 모든 경우의 수를 확인해야 한다는 관찰을 할 수 있으며, 이것은 백트래킹으로 문제를 풀 수 있음을 알 수 있습니다.
문제에서 조심해야 할 점은 캔이 1개가 있을 때, 랑이 혹은 메리가 캔 1개를 먹으면 나머지 고양이는 해당 캔을 못 먹도록 처리를 해줘야 하는 것입니다.

---

3) 짱해커 이동식

이 문제의 입력값을 보면 비용이 10^9 이하의 정수이기 때문에 완전 탐색으로는 확인할 수 없는 말도 안되는 값임을 알 수 있습니다. 그래서 이동식이 가장 높은 비용의 최솟값을 구할 때 이진탐색을 통해 문제를 풀 수 있습니다.
이런 문제를 구하는 것은 이미 백준에 많은 문제들이 있기 때문에 제가 문제를 풀자마자 기억났던 문제를 링크로 올려드리겠습니다. 작년에 학회에서 모의테스트를 진행할 때 못 풀었던 문제인데, 풀이를 듣고 이렇게도 풀 수 있구나하고 인상 깊게 느껴졌던 문제였네요.
https://www.acmicpc.net/problem/2613

2613번: 숫자구슬

---

4) 비행기 전시

이 문제 코드를 짰을 때는 A형 문제를 풀 때처럼 메모장이나 연습장에 어떻게 코드를 작성할지 기록을 하면서 풀어야 실수를 하지 않고 풀 수 있는 문제였습니다. 하지만 삼성 A형 문제 코드 분량을 뛰어 넘는 코드량이 나오고 있고, 예제가 많은 이유도 나올 수 있는 경우의 수 때문에 예제가 왜 이렇게 나오는지 이해도 했어야 합니다. 그래서 출제진과 이야기를 했을 때에도 이 문제를 풀려면 비행기 전시 이후에 나온 문제들을 푸는 것은 포기해야 할 것 같다고 말은 했었는데, 아마 많은 분들이 이 문제 코드를 짜다가 시간을 많이 날렸을지도 모르겠네요.

---

5) Shooting Game

비행기는 오른쪽 이동, 왼쪽 이동, 공격을 할 수 있고, 운석의 수는 작은 값이 주어집니다.
아마 이 문제를 읽은 분이라면 다들 BFS까지는 생각할 수 있다고 봅니다.
하지만 BFS 코드를 작성하고, 예제 데이터를 넣어보면 틀린 답이 존재하게 됩니다. 이것을 분석해보면 운석을 파괴한 순서에 따라 BFS를 구해야 할 수 밖에 없다는 것을 알게 되고, 아니면 메모리 초과로 충분히 알 수 있습니다.
그래서 메모리 초과를 피하면서 모든 경우의 수를 확인해야하기 때문에 이 문제는 비트마스크를 적용하여 문제를 풀어야 합니다.
비트마스크를 적용하는 기법은 우리 학교 사람들이 잘 모르는 기법이기 때문에 이걸 풀 수 있을까 생각이 들었습니다. 하지만 출제진이 예상한 최상위권 팀에 참가하는 멤버들이 풀은 문제 기록들을 살펴봤는데, 각 팀마다 한명씩은 BFS + 비트마스크 문제를 풀었기 때문에 문제가 없다고 판단했어서 딱히 이야기를 꺼내지 않았던 기억이 나네요.
참고로 비트마스크 + DP로도 풀 수 있습니다. 생각해보니 이 방식으로 푸는게 BFS + 비트마스크보다 더 쉬울 것 같습니다.

---

6) 장난감 섞기

문제를 검수 할 때 재밌게 풀었던 문제입니다.
유형은 금광 세그라는 다이아 5 금광이라는 문제에서 나온 알고리즘 유형이라는데, 금광 세그는 말 그대로 세그먼트 트리를 사용해서 풀어야 하는 문제고, 이 문제는 세그먼트 트리를 사용하지 않고 푸는 문제입니다.

저는 금광 문제를 풀지 않아서 이런 유형이 있는지 모르고 있었습니다. 근데 유형을 몰라도 문제를 해결했어서 딱히 문제 없을 거라고 생각했네요.

[장난감 순서 정하기]
모든 경우의 수를 확인해야하기 때문에 10!은 연산이 필수적으로 필요합니다.

[장난감 1개에서 얻을 수 있는 경우의 수]
1) 맨 오른쪽 요소를 포함한 연속합 (누적합)
2) 맨 왼쪽 요소를 포함한 연속합 (누적합)
3) 모든 요소를 포함한 연속합 (누적합)
4) 중간에 있는 요소가 포함된 연속합 (DP)
총 4가지의 경우의 수가 나오게 됩니다.

[장난감을 합칠 때]
1) 현재 장난감에서 왼쪽 요소를 포함한 연속합이 답이라면 이전 장난감에서 맨 오른쪽 요소를 포함한 누적합 혹은 모든 요소를 포함한 연속합중에 하나를 선택해야 답이 될 수 있습니다.
2) 현재 장난감에서 오른쪽 요소를 포함한 연속합이 답이라면 이전 장난감에 있던 누적합은 답이 될 수 없기 때문에 여기서부터 다시 해당값을 시작으로 출발합니다.
3) 모든 요소를 포함한 연속합이 답이라면 이전 장난감에서 맨 오른쪽 요소를 포함한 누적합 혹은 모든 요소를 포함한 연속합중에 하나를 선택해야 답이 될 수 있습니다.
4) 중간에 있는 요소를 포함한 연속합이 정답이라면 해당 장난감만 사용하는 것이 정답입니다. 왜냐하면 오른쪽 요소부터 시작하는 누적합을 2)에서 이미 확인했고, 왼쪽 요소부터 시작하는 누적합도 1)에서 이미 확인했기 때문입니다.

이렇게해서 코드를 작성하여 문제를 풀 수 있었습니다.

---

4. 대회 피드백

---

이번 대회의 문제점을 생각해보니 여러가지 요인이 있던 것 같습니다.

참가자

• 작년에 알고리즘 대회를 개최했으니 올해는 참가자들 실력이 좀 더 늘어났을 거라는 생각
• 생각외로 백준에서 문제를 많이 푸시는 교내 학생 분들이 의외로 많이 참여를 하지 않음

문제 출제

• 시뮬레이션 문제가 너무 어려움
• 예상 티어를 낮게 잡음
• 문제 지문은 최대한 짧고 문제를 읽자마자 바로 이해할 수 있도록 만들어야함

---

 

5. 대회를 마치며

---

대회 개최를 준비하는 활동은 코딩만 계속하다가 취업하는 컴공이라면 흔치 않은 경험이기도 합니다. 하지만 생각외로 사람에 대한 스트레스를 너무 많이 받아서 한 번이면 좋은 경험했다라고 말할 수 있지 두 번은 절대 못할 것 같네요.

내년에도 대회가 개최된다면 문제만 만들 예정인데, 내년엔 시간 소비를 많이 하지 않도록 미리미리 준비를 해야겠습니다.

내년 대회도 파이팅!

---