Coding House Competition 2023-2024 개최 후기

제가 드디어 대회를 개최하는 날이 오네요. 큰 공식 대회는 아니고 교내대회이긴 하지만, 첫 경험인만큼 저에겐 매우 중요하고 가치있는 경험이었습니다. 저 혼자서 14문제 모두 만들었고, 대학 원서 넣고나서 좀 여유 생긴 13학년 선배들한테 대회 당일 날 감독만 도와달라 요구했습니다. 생각보다 학생들 모두 되게 잘해주었고, 저도 출제자, 개최자로서 굉장히 뿌듯하다 느꼈습니다.

무엇보다도, 학생들의 실력 인플레이션이 많이 올랐다고도 느껴지는게 작년에 선배들이 개최했던 대회에선 총 15문제 중 많이 푼 팀이 대략 7솔 정도 했던 걸로 기억합니다. 올해는 제가 Division을 2개, Easy와 Lunatic으로 나누었는데요, 각각 10문제로, Easy 1위가 9솔, Lunatic 1위가 8솔을 함으로써 참가자 학생들이 엄청나게 큰 발전을 보여주었습니다. 

대회 플랫폼은 Hackerrank를 사용했습니다. 대회 개최에 있어서 무난한 플랫폼이였고, 작동 원리도 간단했기에 개최자, 참가자 모두 조작하기 쉬웠습니다. 

Easy Division: https://www.hackerrank.com/contests/house-competition-2023-2024-easy/challenges
Lunatic Division: https://www.hackerrank.com/contests/house-competition-2023-2024-lunatic/challenges


솔직히 우려가 많았습니다. 그리고 그 우려는 어느정도 사실이 된 거 같습니다.

???: 이거 그냥 개인 사심 채우려고 대회 연 거 아니냐
→ 반박불가. 맞습니다

???: 이상한 설정 좀 넣지 마라
→ 미안합니다

???: 올해도 4번의 저주를 피하지 못했네
→ 미안합니다 x 2

 

Easy Division의 4번이자 Lunatic Division의 1번이였던 Bustling Marketplace 문제의 경우, 웹사이트 오류(?)로 인해 잘못된 지문(수정 전 지문)이 공개되어 참가자들이 맞왜틀을 당하며 많은 시간을 버리게 되었습니다. 작년 House competition 때 4번 문제의 지문이 SAT급으로 거지 같았어가지고 제가 출제자한테 뭐라 했었는데(친한 선배라 장난 좀 친 겁니다) 올해 4번은 아예 문제 자체가 틀려버린, 작년의 4번보다도 심각한 최악의 4번이 되어버렸네요... 할 말이 없습니다. 제 책임이고 제 잘못이 맞습니다. 대회 끝나고 참가자들한테 도게자 박았습니다. 다행히 대회의 결과에는 큰 영향이 있지 않았습니다. 

나름 검수한다고 한 거였는데 저장 버튼을 눌렀는데도 지문이 수정 전 버전이 올라갔던 건 좀 예상외였습니다. 시험 볼 때도 마찬가지지만 대회를 개최할 때도 검토를 끊임없이 해야한다는 것을 깨달았습니다. 

---

문제해설 

TMI) 동덕들은 눈치 채겠지만 이번 대회의 문제들은 모두 동방을 모티브로 만들어진 문제들입니다. 

1. Udongein  

- Easy Division 1번
- 알고리즘: 사칙연산

 

레이센이 가지고 있는 돈: a
우동 한 그릇의 가격: b

두 개의 숫자 a, b를 입력 받아서 
a를 b로 나누었을 때의 몫을 출력하면 정답

 

2. Broken Moon  
- Easy Division 2번
- 알고리즘: 사칙연산

N명의 사람들 중 달보다 큰 밀도를 지닌 사람이 달을 부순 범인
모든 테스트 케이스에 대하여 항상 한 명의 범인만이 존재한다고 주어짐
입력받은 사람 중에 달의 밀도보다 큰 밀도를 가진 사람의 이름을 출력


3. Unconscious Hartmann  
- Easy Division 3번
- 알고리즘: 브루트포스 알고리즘

2중 for문 브루트포스를 돌려서 각 숫자의 두뱃값이 배열에 존재하는지 확인만 하면 됨.
N의 크기가 작기 때문에 O(n^2)으로 가능.

 

4. Bustling Marketplace  
- Easy Division 4번 / Lunatic Division 1번
- 알고리즘: 그리디 알고리즘

4번의 저주를 피하지 못한 제작자 공인 쓰레기 문제. 
문제 자체는 굉장히 간단함. 
5 종류의 동전 중 가장 값이 높은 500원부터 차례로 써가면 됨.


5. Яeverse
- Easy Division 5번
- 알고리즘: 정렬

입력받은 여러개의 테스트 케이스(배열들)을 그냥 오름차순 정렬한 뒤 출력하면 되는 간단한 문제
너무 간단한 문제였다. 


6. Faraway voyage of 380,000 kilometers
- Easy Division 6번 / Lunatic Division 4번
- 알고리즘: 구현

간단한 쿼리 처리 문제.
처음에 입력받는 요정들의 전투력을 배열에 저장한 후, 쿼리를 하나씩 입력받으며 1번 쿼리라면 요정의 전투력을 업데이트, 2번 쿼리라면 특정 구간 내의 전투력 총합을 구하면 된다.
N의 크기가 작기 때문에 시간복잡도를 딱히 고려할 필요도 없다. 

TMI) 지구와 달 사이의 거리는 38만 킬로미터이다.

 

7. Undefined Fantastic Object
- Easy Division 7번 / Lunatic Division 5번
- 알고리즘: 출력

알고리즘이라 할 것도 없다. 그냥 예제 출력에 있는 UFO의 이미지를 복붙해서 Text 언어로 제출하면 되는 날먹 문제.
공짜로 점수 주려고 만든 문제이다. 


8. Bhava-agra
- Easy Division 8번 / Lunatic Division 2번
- 알고리즘: 브루트포스 알고리즘, 누적합, 슬라이딩 윈도우

일단 누적합 + 투 포인터를 노리고 만든 문제이긴한데 Hackerrank에 문제가 생겼는지 1만이 넘는 케이스를 등록하지 못함. 이 부분에 대해서 직접적으로 문의도 넣어봤지만 대회 종료 2주가 지났는데도 연락을 못받음. 

즉, 시간초과를 겨냥했던 문제였지만 브루트포스만 쓰더라도 풀리게 그냥 냅뒀음. 사실상 강제적인 디플레이션을 맞이한 피해자 문제

브루트포스로 대충 구간별 탐색 돌려서 a[i]+a[i+1]...+a[i+M-1]의 최댓값 구하면 끝. 


9. (9)
- Easy Division 9번 / Lunatic Division 9번
- 알고리즘: 문자열

                                              ???: “문제의 순서는 난이도를 기준으로 정렬되어있지 않습니다.”
문순난정의 정점 문제. 
치르노가 바보라는 컨셉답게 9번 문제지만 굉장히 허접한 문제이다. 
숫자를 문자열로 입력받은 뒤, ‘9’가 몇 개 포함되어있는지 갯수만 세면 끝인 문제
사실상 Lunatic Division에서 가장 쉬운 문제 중 하나이다. 
하지만 9번이라는 후방 배치로 인해 생각보다 이 문제를 못 봤을 참가자가 많았을 것으로 예상. 


10. Jelly Stone
- Easy Division 10번 / Lunatic Division 3번
- 알고리즘: 게임 이론, 다이나믹 프로그래밍 

DP로 게임의 승리 상태를 저장해서 대충 몇 번 돌려보면 처음에 돌의 갯수가 홀수인 경우에는 레이무가, 짝수일 때는 마리사가 이긴다는 걸 알 수 있음.
???: 어 이거 돌 게임 아닌가요

 

11. Grandma's Portal
- Lunatic Division 6번
- 알고리즘: 그래프 이론, 깊이 우선 탐색, 너비 우선 탐색, 애드 혹, 그리디 알고리즘, 다이나믹 프로그래밍

이 문제는 풀 수 있는 방법이 매우 다양하다. 어느 방법을 사용하건 상관없지만, 반례를 잘 고려할 필요는 있다. 

일단 시작하자마자 할머니 집에 도착이 불가능한지 부터 검사해야함. 혹여나 할머니 집으로 갈 수 있는 모든 경로에 대하여 벽이 세워져 있다면, 바로 -1을 출력하고 프로그램 종료.

포탈을 쓰는 경우와 안쓰는 경우로 나눌 수 있는데, 포탈을 안쓰는 경우야 그냥 dfs 돌려서 구하면 되고, 포탈을 쓰는 경우에는 다음과 같이 코드를 짜면 된다:

• (0,0)에서 각각의 포탈까지 가는 데에 걸리는 시간 중 최단시간을 X라고 하자
• (n-1,n-1)에서 각각의 포탈까지 가는데에 걸리는 시간 중 최단시간을 Y라고 하자

포탈을 안쓰고 목적지까지 가는데에 걸린 최단시간을 Z라고 하였을때, 정답은 다음과 같다:  min(z, x+y)

12. Judge
- Lunatic Division 7번
- 알고리즘: 논리, 구현

범인이 여러 명일 수 있거나, 사람들의 주장을 모두 듣고나서조차 논리적으로 범인이 누구인지 알아내는 게 불가능할 경우, -1을 출력해야함. 

우선 절대로 거짓말쟁이일 수가 없는 주장이 존재하는지 찾아봐야함. 
만약 똑같은 주장이 1개 이상일 경우, 해당 주장을 하는 사람들은 모두 거짓말쟁이가 아님
왜냐하면 거짓말쟁이는 항상 1명만 존재하기 때문에, 만약 똑같은 주장을 하는 사람이 2명 이상인데 그 중 한 명을 거짓말쟁이라고 지정하면 모순이 발생함.

무조건 참인 사람들을 걸러낸 후에, 나머지 사람들이 각각 거짓말쟁이일 경우로 하여금 모든 경우의 수를 다 찾아보면 됨. 


13. Crazy Backup Dancers
- Lunatic Division 8번
- 알고리즘: 다이나믹 프로그래밍, 배낭 문제

가장 기본적인 간단한 배낭 문제이다. 
춤 동작을 고를 때, 현재 내 스테미나보다 해당 춤동작의 스테미나 소비 수치가 더 크다면 고르지 않는다.
만약, 그렇지 않다면, 현재 선택한 춤동작의 스테미나 수치만큼 기존에 선택한 춤동작들을 뺀 후 선택한 춤동작을 플랜에 넣었을 때의 총 가치와, 현재 춤 동작을 하지않기로 하고 이전 플랜을 그대로 가지고 갈 때의 총 가치 중 더 큰 쪽을 택하면 된다. 

 

14. Faith is for the transient people
- Lunatic Division 10번
- 알고리즘: 기하학, 볼록 껍질

문제에서 말하는 다각형(사나에가 규칙을 따르며 방문할 신사들의 위치를 이었을 때 만들어지는 다각형)이 볼록껍질의 성질을 띈다는 것을 알 수 있음. 

y 내림차순, x 오름차순으로 정렬하여 기준점을 구하고, 나머지 좌표들을 기준점에서 시계 방향으로 정렬하여 볼록껍질을 만들어주면 간단하게 풀리는 문제.