티스토리 뷰

제 1회 UNIST 알고리즘 프로그래밍 경시대회 Uni-CODE에서 출제, 검수 및 운영의 일부분에 관여하였습니다. 문제들은 다음 링크에서 확인할 수 있고, 대회를 개최하는 과정에서 느낀점과 문제에 대한 풀이를 간략히 적어보았습니다.

(Update: 풀이 파일도 추가했습니다.)

main_solution.pdf
0.73MB

 

https://www.acmicpc.net/category/detail/2105

Solution

문제들에 대한 풀이를 간략히 적어봤습니다.

A. 커맨드

박원님이 출제하신 문제로, 가장 쉬운 문제입니다. 문자열을 입력 받고, 조건을 만족하는 문자열인지 조건문을 통해 판별하면 되는 문제입니다. 많은 사람들이 쉽게 해결했습니다.

B. Baba is Rabbit

제가 출제한 문제입니다. 주어진 사물들을 적당한 자료구조(map/dict 등)를 이용하여 정수에 대응시켜 그래프를 구성한 후, 그래프 탐색을 통해 해결할 수 있는 문제입니다.

DFS/BFS 등의 그래프 탐색과 문자열 입출력, 그리고 자료구조의 간단한 활용을 할 수 있는지 묻는 문제였습니다. 개인적으로는 매우 쉽다고 생각했으나, 문자열 처리에 익숙하지 않은 분들이 많은 오답을 내셔서 아쉬웠습니다. 그 외에는 map 등을 이용하여 그래프의 adjacency list를 표현하려 하다가 메모리 초과를 받은 분들이 조금 있었습니다.

참고로, 총 시간복잡도는 $O(N \log N)$입니다.

C. 피보나치 음악

저와 박원님이 출제한 문제입니다. 박원님이 들고오신 초안은 BigInteger 클래스 없이 해결할 수 없는 문제였어서, 제가 아예 새로운 문제로 뜯어 고쳐 현재의 문제가 나왔습니다.

피보나치 수열을 $\{f_n\}$이라 할 때, $\{f_n \mod M\}$은 $M^2$ 이하의 주기를 가짐을 비둘기집의 원리를 통해 증명할 수 있습니다. 이를 활용하면, 새로운 수열 의 주기가 $4M^2$ 이하임을 알 수 있고, 이를 통해, $O(M^2)$ 시간에 새로운 수열을 1주기 만큼 구해놓고, 이후에는 쿼리당 $O(1)$에 처리할 수 있습니다. 시간복잡도는 총 $O(M^2+Q)$가 됩니다.

개인적으로는 간단한 관찰과 규칙성을 통해 해결할 수 있는 쉬운 문제라고 생각했으나, 문제를 제대로 읽지 않은 사람이 생각보다 많았고, 구현에 있어 off-by-one error 등에 힘들어 하는 참가자 또한 많았습니다. 대회가 끝나고 나니 예시 입출력으로 $M \ge 10$인 경우를 하나 줬으면 더 좋을 것 같다는 생각이 들었네요.

D. UNIST는 무엇의 약자일까?

제가 출제한 문제입니다. D[i][j]를 첫 i개의 단어를 이용해서 만든 문자열이 UNIST의 길이가 j인 prefix가 되는 경우의 수로 정의한 뒤, 동적 계획법을 활용하여 해결하면 됩니다.

초보자들이 쉽게 풀 수 있는 문제라 생각하여 출제했지만, 의외로 많은 사람이 이 문제를 어렵게 접근했던 것 같습니다. 실제로 대회 중에 제출도 적었고, 맞은 사람도 적어서 아쉬웠습니다.

E. 버스 노선

안윤표님이 출제하신 문제입니다. 주어진 그래프의 차수가 1인 정점의 수를 $t$라 하면, $\lceil \frac{t}{2} \rceil$이 답이 됩니다. 이는 수학적 귀납법으로 쉽게 증명할 수 있습니다.

규칙을 찾아 proof-by-ac로도 해결할 수 있는 문제이기도 했다고 합니다. 그래서인지, 개인적으로는 C번보다 어려운 문제라고 생각했지만, 다른 분들의 의견은 정반대였습니다.

F. 시계

이서윤님이 출제하신 문제입니다. 대회에서 두 번째로 쉬운 문제로, 열심히 사칙연산을 잘 하면 해결할 수 있습니다. 다만, 출력 과정에서 소숫점 아래 부분이 누락되어 오답을 받은 경우가 종종 있었던 것 같습니다.

G. 복붙하기

박서영님이 출제하신 문제입니다. 처음에는 $N \le 10,000$이었으나, 신승원님이 문제의 제한을 수정했고, 김현수님과 제가 정해를 작성했고, 제가 데이터를 만들었습니다.

이 문제는 결정문제로 바꾸어 답에 대한 이진탐색을 통해 접근하는 것이 용이합니다.

"답이 $X$ 이상인가?" 라는 결정문제를 해결하는 것은 크게 두 가지 방법이 있는데, Suffix Array와 LCP를 이용하는 방법이 있고, 또 다른 방법으로는 Rabin-Karp 해싱을 이용하는 방법이 있습니다.

각각 총 $O(N \log N)$, $O(N \log^2 N)$ 시간에 문제를 해결하게 됩니다. 대회 중에 해결한 분들은 모두 해싱을 이용했습니다.

H. 수강 과목

이서윤님이 출제하신 문제입니다. 전형적인 0/1-냅색 문제로, 풀이법이 널리 알려져 있습니다.

하지만, 의외로 많은 사람들이 해결하지 못한 문제였습니다.

후기

사실 이 대회를 개최하기 위해 노력하는 과정을 옆에서 지켜본 바로는 대회의 성공적인 개최에 가장 큰 도움을 준 것은 후원사들이 아닌가 싶습니다. 플랫폼을 제공해주신 스타트링크와 후원해주신 삼성 소프트웨어 멤버십, 네이버/NHN에 감사의 말씀을 아끼지 않고 싶습니다. 덧붙여, 저와 함께 외부인으로 수고해주신 김현수, 신승원님께도 감사의 말씀을 드리고 싶습니다.

그리고 이런 대회에 출제하면서 제가 성장할 기회를 주신 UNIST HeXA에도 감사를 표하고 싶습니다.

하지만, 아쉬운 점 또한 있었습니다. 원래 출제자가 데이터를 만들어야 하지만, 폴리곤 사용의 미숙으로 인해 데이터가 너무 약한 관계로 절반 이상의 데이터를 제가 새로 만들었습니다. 그리고, 데이터 제작을 대회 개최 직전에 너무 빠듯하게 진행했던 점 또한 아쉬웠습니다.

'일상' 카테고리의 다른 글

제 1회 Uni-CODE 에디토리얼 및 후기  (3) 2019.11.03
연인 관계의 수에 대한 짧은 이야기  (1) 2019.10.25
위스키  (0) 2019.10.21
KAIST 9th ICPC Mock Competition 참가 후기  (0) 2019.10.04
UCPC 2019 온라인 예선 후기  (0) 2019.07.29
UCPC 2018 연습 후기  (0) 2019.07.27
댓글
  • 프로필사진 코딩강아지 ㄷㄷ 하네요 2019.11.03 02:30 신고
  • 프로필사진 코딩강아지 서픽스 어레이의 LCP만 이용하면 힘들고..
    각종 스위핑과 그래프 이론을 이용을 잘 해야 하더라고요.
    쉬운 쪽은 라빈 카프인 듯 싶네요.
    |str| = 100만이였다면 난이도는 껑충이였을 거 같네요.

    처음 제출이 맞았지만 금방 저격 케이스 찾아서 (aaaabbbb)
    다시 풀었어요.
    2019.11.05 16:58 신고
  • 프로필사진 123 전반적으로 문제가 좀 어려웠어용.. 게시자님께서 올린 문제도 틀리고ㅠㅜ아직 실력이 한참 부족한가봅니다ㅠㅠ 2019.11.12 10:35
댓글쓰기 폼