구데기컵 x solved.ac 콜라보 카페 후기

Thu Apr 06 2023

후기를 쓸까말까 고민을 좀 했었는데 우연찮게 과제가 없는 날이 생기기도 했고, 블로그를 개편한 이후로 아무 글도 쓰고 있지 않던 상황을 좀 타파해보고자... 후기를 쓰기로 했다.

올해도 돌아온 구데기컵 시즌에, 구데기컵 예비소집이라는 걸 쳤다. 그리고 4/1일과 4/2일 주말에 이틀에 걸쳐 구데기컵 x solved.ac 콜라보 카페가 열린다는 공지가 떴다. 마침 집에서 굉장히 가까운 위치에서 열리는 데다가 한별이 굿즈와 스태프와의 대결이라는 컨텐츠도 있겠다 이틀 다 방문하기로 생각했다. 그리고 바로 같이 갈 ps러들과 일반인들을 모집해서 이틀 다 혼자 가지는 않게 되었다.

카페 방문 전

공지를 보자마자 든 생각은 대충 키링을 몇 개를 질러야 하나에 대한 고민과, 대결 중에 하나 정도는 준비를 해볼까하는 생각이었다. 체스는 딱히 해본 적이 없어서 바로 걸렀고, 가위바위보는 상대방이 내기 전에 근육의 움직임을 보고 이긴다는 사람들이 존재한다는 건 알지만 그 사람이 나는 아닐 거 같아서 운에 맡기기로 했다. 그래서 남은 건 랜덤 브5와 소인수분해인데, 처음에 소인수분해 룰을 보고 키파님이 자동차 번호판 소인수분해하는 취미가 있으신가 의문이 들었다. 왜냐면 내가 가끔 그러기 때문이다. 그렇지만 속도는 별로 자신이 없었기에 일단 랜덤 브5를 준비하려고 시도했다.

랜덤 브5

우선 ps할 때 c++을 사용하는 사람으로써, 두 가지 옵션이 떠올랐다.

c++보다는 짧게 짤 수 있는 python, ruby 등의 언어 배우기
Golfscript 배우기 처음에는 최대한의 시간 격차를 만들기 위해서 golfscript를 배우는 걸 시도했다. golfscript의 공식 페이지는 여기인데, 보면 알겠지만 처음 보고 이해하기가 꽤 어려운 사이트였다. 그래서 일단 브5들을 풀고 숏코딩 상위권에 계신 분들의 코드를 보고 기능을 하나씩 익혀가는 방향으로 접근했다.

A+B이나 A-B 정도는 쉽게 시작했는데, A/B부터는 정신이 아득해졌다. 이 문제의 경우 실수 나눗셈을 \(10^-9\) 정밀도로 시행하는 문제인데, golfscript는 기본적으로 정수로만 연산을 할 경우 실수 나눗셈으로 계산하라는 명령이 없는 걸로 알고 있다. 실제로 숏코딩 코드는 다음과 같다.

~.9~.??*/

이 코드는 우선 두 개의 정수를 입력받고, \(b\)를 복사해서 스택에 하나 더 끼워넣는다. 그 이후 어떻게 잘 \(10^{-10}\)이라는 값을 넣고 \(b\)의 power로 넣어서 스택에 순서대로 \(a\), \(b\), \(b^{10^{-10}}\)라는 값을 집어넣어둔다. 마지막으로 맨 위 두 수를 곱하고 \(a\)를 나눠주면, 문제에서 요구하는 정밀도 안으로 들어올 정도로 \(b\)에 가까운 실수로 정수를 나누는 모양새가 되어서 최종 결과물이 실수로 처리된다.

이 문제를 보자마자 바로 마음이 꺾여버렸다. 신기하다는 생각은 들었는데 굳이 더 알아보고 싶지는 않은 정도의 지식이어서, 브5에서 문제번호 순서대로 이 문제까지만 공부하다가 브5 대결은 그냥 포기했다. 단순히 golfscript가 어려워서라기보단 Ada나 Visual Basic 같은 언어로 언어제한이 걸린 문제들도 많다는 걸 깨달았고, 일본어 러시아어 등 다국어 문제들이 있다는 점에, 승리 보상인 한별이 씰스티커도 예전에 대회 상품으로 받은 적이 있었기 때문에... 브5 대결을 깔끔하게 포기하게 만드는데 한몫했다.

소인수분해

그렇게 소인수분해 대결을 준비하게 되었는데, 사실 랜덤 브5를 포기한 이후로 이벤트 날 거의 직전까지 아무것도 안 하고 있었다. 다만 이벤트 이틀 전에 갑자기 준비를 하게 되는데, 그 배경을 설명해보겠다.

제곱근 빠르게 치기(?) 게임

콜라보 카페와는 완전히 독립적인 사건으로, 대략 한 달 전 필자의 친구가 뜬금없이 C++ reserved word 빠르게 타이핑하기 대결을 들고 온 적이 있다. LLaMA 레포를 보다가 발견했다고 한다. 옛날 한컴타자연습에 있던 게임처럼 멀티플레이어가 같은 라운드에 접속하여 화면에 보이는 여러 단어들을 먼저 쳐서 점수를 획득하는 게임이다. 그리고 지금은 본인의 서버에 따로 호스팅까지 하고 있다! 그런데 나는 C++ 커맨드 입력보다는 그 옆에 있던 또다른 게임인 제곱근 치기 게임에 더 관심이 생겼다. 예를 들어 화면에 169라는 수가 떠 있으면 13을 입력하면 되는 식이다. 처음 해봤을 땐 재밌겠다 싶어서 그냥 해봤는데, 생각보다 많이 어렵길래 뭔가 승부욕이 발동해서 싱글플레이로 점수를 얼마나 얻을 수 있나 연습을 좀 했고, 한 3~4일 정도 파니 300점을 넘길 수 있었다.

그래서 만약에 소인수분해 대결에 대략 1% 정도 확률로 제곱수가 나온다면 무조건 이길 수 있지 않을까라는 생각이 들었고, 이 때까지만 해도 '운 좋으면 이기겠지~'라는 마인드였다. (이 때까지만 해도 대결의 정확한 룰이 공개된 시점이 아니라서, 수 '하나'를 랜덤으로 뽑아서 먼저 분해하기인줄 알았다) 소인수분해 연습 프로그램을 만들어볼까도 생각했는데, 귀찮아서 포기한 상태였다.

카페 2차 공지

콜라보 카페의 추가 공지가 아마 목요일에 올라왔던 것으로 기억하는데, 나는 그 때 우연찮게 방금 전 언급한 친구와 저녁을 같이 먹고 있었다. 그런데 그 때 추가 공지가 올라와서 세부 룰이 공개되었고, 대화의 소재로 채택되어서 어떤 자잘한 팁들이 있을지 제대로 생각해보는 시간을 가졌다. 먼저 어떤 수를 소인수분해할 때, divisor만 알면 되고 quotient를 계산하지 않아도 된다. 또 \(23^3 > 10000\)이기 때문에, 만약 소인수분해가 3번 이상 되는 수라면 무조건 19 이하의 소인수가 있다. 그래서 \(n=pq < 10000\)꼴 분해를 전부 외울 수 있나 고민했는데, 외워야 하는 수는 굉장히 많기 때문에, \(p < q < 100\)이라는 조건을 하나 더 붙여서 외워보기로 했다. 그러므로,

주어진 수가 분해법을 알고 있는 수라면 ok.
2, 3, 5, 7, 11, 13, 17, 19로 직접 나눠보기를 시도한다. 나눠지면 ok.
그게 아니라면 평상시와 같이 23부터 시작하여 \(O(\sqrt{n})\) 소인수분해를 시도한다.

그렇게 흥미로운 lookup table이 생성되었다. 그리고 저 테이블을 범위로 가지는 소인수분해 게임이 아까의 제곱근 치기 게임 사이트에 추가되었다! @goranmoomin이 적당히 원래 소스를 보고 추가해주었다.

남은 문제는 저 테이블을 주말 전에 다 외울 수 있느냐인데, 나도 내 암기력의 한계가 궁금해진 김에 일단 시작을 했다. 그리고 정신 차려보니 금요일이 삭제되어 있었다. 덕분에 \(O(1)\)에 소인수분해가 가능해진 숫자가 대략 200개 정도...가 된 채로 준비를 끝냈다.

난 이 때까지만 해도 구데기컵이 4/1에 열릴 줄 알았다. 구데기컵이니까 공지에 적힌 날짜가 페이크겠지 싶었는데, 생각해보니 그 운영진들이 카페에서 스태프로 있다는 건데 대회가 안 열리는 게 맞겠네라는 결론에 도달했다.

카페 방문

슬프게도 사진은 얼마 못 찍었다.

첫째 날 방문

합정역에 도착을 해서 골목으로 들어가려는데, 뭔가 목적지가 같을 것으로 추정되는 무리를 만나서 따라가봤더니 카페에 도착했다(??). '노머글얼라우드'가 뭔 뜻인지 몰랐는데 'No muggle allowed'인걸 보고 이런 거 전문 카페인가 싶었다. 어찌 됐건 기다리면서 오늘치의 말해보카를 돌고 있었는데, 보통 몇십 분이 걸리는 작업이 거의 끝나갈 때까지도 카운터가 멀리 있었다.

카페 안쪽으로 들어가서는 콜라보 느낌을 주는 소품들을 보게 됐는데, 우선 계단부터 시작해서 카페 입구까지 오른쪽 벽에 카페 포스터랑 역대 구데기컵의 로고(?)가 붙어있었다. A4 한장에 하이퍼 뭐시기 그림이 있는 걸 보니 마음이 편안-해졌다. 그리고 그 외에 기억에 남는 건 노래 선곡이 심상치 않았다는 것과, 이 카페의 원래 소품들이다. 처음에는 음악이 있다는 사실을 몰랐는데, 갑자기 수련의 숲 bgm이 들려오길래 그 뒤로는 좀 신경써서 들어봤다. 카페 안쪽으로 줄이 줄어들어서 보니까, 스파패의 아냐 쿠션으로 시작해서 정확히는 모르겠는데 원피스 캐릭터 중 하나로 추정되는 피규어가 있었고, 나히아랑 주술회전인 것으로 추정되는 뭔가도 있었다. 천장엔 한별이 엽서가 달려 있었고 귀칼 포스터도 봤던 기억이 있다. 그 외에 것들은 잘 모르겠다. bgm들은 어디선가 들어본 게 많았다. 열심히 기억을 더듬어서 목록을 만들고 있었으나... 글 쓰는 도중에 플레이리스트가 공개되었다.

여튼 말해보카와 음악을 들으면서 줄서있는데, 1일 1특전과 랜덤 티어 아크릴이 전부 소진되었다는 슬픈 소식을 듣게 되었다. 그리고 이건 이틀차에 오픈 전에 줄을 서 있게 만드는 동기가 되었다. 그렇게 한 시간 정도를 기다려서 주문을 하고, 옆에 있는 스태프 존으로 이동해서 맨처음 havana님과 가위바위보 대결을 했다. 뭔가 내기 직전에 예감이 좋았는데, 가위로 이겨서 구데기 스티커를 획득했다.

그리고 대망의(?) 소인수분해 대결을 위해 줄을 서 있었는데, 앞에서 하고 있던 대결에 뜨는 수를 보고 뇌를 좀 예열해봤다. 그렇게 조금 기다리고 시작을 했다. 내 기억이 맞으면 중간에 7348이 나왔는데, 4로 나누면 1837이 나온다. 이 다음 소인수는 11인데, 너무 긴장해서 그런지 엔터를 이상하게 쳐버렸다. 먼저 끝나긴 했으나, 키파님이 WA(?)나 TLE(?) 없이 마무리하시면서 졌다. 끝나고 생각해보니 문제로 나오는 수들이 좀 이상할 정도로 소인수 개수가 많고, 소인수들이 대체로 작은 것 같았다. 그래서 균등분포로 수를 뽑는 건 아니라는 생각이 들었다. 이후에는 어떻게 잘 자리를 잡아서 위상수학 과제 및 뒤에 합류한 친구들과의 수다를 떨다가 귀가했다. 카페에서 잘 안 보이는 뒤쪽 길로 나가면 합정역-상수역 사이 경로에 벚꽃이 만개해있었다.

둘째 날 방문

어쩐지 이 날에도 아침에 일정이 있었으나, 놀랍게도 그 일정이 합정 근처여서 간단하게 점심을 처리했다. 그리고 오늘도 카페에 갈 거 같은 사람들을 따라갔더니 도착하는데 성공했다. 도착한 시간이 11:27인가 그랬는데도 내 앞으로 15명은 서 있었는데, 설마 이튿날에 열기가 더 뜨거울 줄은 몰랐다. 심지어 한 10분 지나니까 내 앞에 있는 수만큼 뒤에 사람들이 왔다. 그러나 일찍 온 덕분인지 자리도 잡는데 성공했고 이벤트도 첫날보다는 여유로운 분위기에서 즐길 수 있었다. 안타까운 점은 첫날 키링을 안 샀는데 재고가 부족해진 탓에 구매 제한이 5개로 줄어들었다는 점이다. 여튼 오늘은 특전도 받는데 성공했고, 럭키드로우까지 뽑으면서 뭔가 손에 들고 있는 게 많아졌다.

그리고 두 번째 소인수분해 대결을 해야 했는데, 뭔가 이 날은 머리가 아프길래 일단 주문한 아메리카노를 좀 마시고 뇌가 정신 좀 차리면 해야겠다라고 생각을 했고, 커피를 마시면서 위상 과제를 잠깐 건드렸다. 그리고 이벤트 대기줄이 없길래 바로 가서 시작했다. 첫날의 경험으로 침착하게만 하면 될 거 같았고, 이번에도 소인수가 작은 수들이 대거 등장하길래 속도가 좀 붙었다. 무엇보다도 내가 외운 lookup table에서 숫자가 하나 그대로 나왔는데, 무려 \(2479 = 37 \times 67\)이 나오면서 시간을 굉장히 많이 아낄 수 있었다.

그리고 오늘의 약속은 2021년의 ucpc, icpc 팀원들이 모이는 약속이 되었는데, @Karuna와 @rubix가 모였다. 12시 정도에 도착한 @Karuna가 줄이 너무 길다고 해서 카페에서 빠르게 나와서 다른 곳으로 이동했다.

결론

이틀간의 방문으로 얻은 전리품(?)들은 다음과 같다.

키링깡(?)도 마스터 키링이 나오는 성공적인 가챠였다! 루4 키링은 내가 루4를 달성하고 달고 다니면 어떨까 싶은 생각이 있고, 플1 키링은 꽤 색감이 잘 나와서 만족스럽다. 혹시나 키링깡을 하기 전에 여기서 나온 최대 티어를 달성하고 ps를 접겠다!라는 내기를 걸었으면 큰일날 뻔했다.

대회가 아닌 오프라인 ps 이벤트가 열릴 줄은 몰랐다. 재밌게 준비해주신 스태프 분들께 감사를 드립니다.

부록

이번에 소인수분해를 빨리 하는 자잘한 팁들을 고민해봤고, 실제로 나는 평소에 어떤 방법으로 소인수분해를 하는가를 정리해두면 좋을 것 같아서 부록으로 뺐다.

먼저 내가 기본적으로 사용하는 방식은 trial division이다. 2, 3, 5, 9, 11은 배수판정법이 있으므로 비자명한 소수들에 대해서 얘기를 해보겠다. \(n\)이 주어졌을 때 \(p\)로 나눠지는지 체크하려면, 수를 빼면서 \(n\)의 자릿수를 낮춰야 한다. 접근법은 크게 두 가지인데, \(n=5651\)이고 \(p=19\)라고 하자.

1900의 배수들 중 \(n\)에 가장 가까운 수를 찾는다. 그럼 이 경우 5700이므로 \(n\)을 빼면 49가 남는다.
일의 자리를 맞춰서 빼도 된다. 19의 배수 중 일의 자리가 1인 수는 171이나 -19이다. 그러면 비자명한 소수들은 10과 서로소이므로 0을 떼버릴 수 있다.

나는 보통 전자의 방법을 선호한다. 이번 대결에서는 아니었지만 만약 몫을 계산해야 하는 경우, 위의 계산 과정에서 빼거나 더한 수들을 역으로 계산하여 몫을 알아낼 수 있어야 한다. 그런데 전자의 방법은 내가 빼거나 더한 수가 그대로 몫의 계산에 반영되는데, 후자는 지금 내가 계산한 값이 그 이전에 몇 개의 0을 뗀 값인지를 한 번 더 생각해줘야 해서 별로 선호하지 않는다. 다만 \(n\)의 일의 자리가 \(p\)의 일의 자리와 같거나 - 부호를 붙여서 같다면 가끔 사용하기도 한다.

이 방법은 \(p\)가 커지면 사용하기 불편하다. \(p\)가 크면 \(p\)의 배수가 뭔지 빠르게 계산하기가 어렵고 \(n\)에 가장 가까운 \(10^k p\)꼴 수가 \(n\)의 자릿수를 최소한 하나 낮춘다는 보장이 없어진다. 그래서 \(p\)가 어느 정도 커지면 \(n\)이 소수가 아닌 경우 다른 소인수와 크기가 비슷하다는 점이므로, 반대로 \(n = a^2 - b^2\)꼴로 해석해서 작은 \(b\) 몇 개에 대해서 테스트를 해본다. 예전에는 제곱수 판별을 해야 해서 별로 선호하지 않았는데, 제곱수를 많이 외우게 되면 굉장히 효과적이라는 걸 체감했다.

그러나 위 두 경우가 모두 좋지 않은 경우도 남아 있다. 예를 들면 \(2479 = 37 \times 67\)이 그 예시이다. 최소의 소인수가 37로 제법 크면서도 합차 공식을 적용하기엔 \(b\)가 적당히 큰 경우이다. 나는 이런 경우에는 어쩔 수 없이 원래 시도하던 trial division을 다시 시행하되, 일단 나눠지는지 판별만 시도한다. \(2479 = 50^2 - 21\)과 같이 가까운 제곱수와 나머지 항의 합으로 \(n\)을 표현하면, mod p에서만 계산하면 되므로 계산 대상이 되는 수가 꽤 작아진다. 37을 테스트한다고 하면 \(13^2-21 = 148 = 0\)만 계산하면 되기 때문. 다만 이 경우 몫 계산은 따로 해줄 수 밖에 없다. 운이 좋아서 \(n = 1847 = 43^2 - 2\)처럼 나머지 항이 1이나 2 정도면, 이차잉여 때문에 테스트할 소수 후보군을 절반 정도로 줄이는 것도 가능하다.

마지막으로 내가 가끔 쓰거나 웰노운인 trick들이 몇 가지 있다.

\(n\)을 앞 몇 자리에서 끊어 읽었을 때, 남은 자리들과의 gcd가 1보다 큰 경우가 있다. 예를 들면 \(2149\)는 앞 두 자리와 뒤 두 자리가 각각 7의 배수이므로 전체도 7의 배수이다. 몫 계산이 깔끔한 것도 장점.
\(1001 = 7 \times 11 \times 13\)이라는 걸 이용해서 7, 11, 13에 대한 테스트를 동시에 하는 방법도 있다. 다만 이 경우 몫 계산을 하려고 할 때 7에 대해서는 143을 곱하고, 11에 대해서는 91을 곱하고, 13에 대해서는 77을 곱하는 등 몫 계산법이 달라진다는 점이 불편해서 잘 사용하진 않는다. 또 1001의 배수를 \(n\)에서 빼는 것은 말 그대로 자릿수만 줄여주고 나머지 백의 자리나 십의 자리를 줄여주지는 못하기 때문에, 계산량 전체를 놓고 보면 크게 차이가 안 날 수도 있다.
37은 테스트하기 꽤 편한 소수이다. \(111 = 37 \times 3\)임을 이용하면 1001으로 자릿수를 줄이는 것처럼 빠른 계산이 가능하다.
Lehman Factorization(참고)의 아이디어로도 사용되고, 실제로 쓴다는 사람도 꽤 있는 방법이다. 예를 들어 \(32849 = 107 \times 307\)이 있을 때, 여기에 3을 곱해서 수를 키우면 합차 공식을 적용하기 쉬운 꼴인 \(98547 = 314^2 - 7^2\)이 되는 것이다. 나는 어떤 수를 곱해야 그 꼴이 되는지가 안 보여서 사용해본 적은 없다.
\(1271 = 31 \times 41\) 같은 수는 \((30+1) \times (40+1)\)로 나타냈을 때 받아올림이 한 번도 일어나지 않는 수이므로 12, 7, 1로 끊어읽을 때 소인수분해 form이 잘 보이기도 한다.
2, 3, 5, 7, 11 정도 해보고 안 되면 소수라고 말해도 대충 맞는다.