리유나의 항해일지

https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmicpc.net 정말로 유명한 문제입니다. 당시 중등부에 이정도 난이도 문제가 나와서 말이 많았다고도 하고, 풀이 자체는 여러 문제에서 유용하게 쓰일 수 있기 때문에 세그트리 응용을 공부할 때 꼭 한번씩은 짚고 넘어가는 문제입니다. 이 문제의 프리퀄 격이라 할 수 있는 연속합과 쿼리(예전에 쓴 블로그 글)를 풀어보신적이 있으시다면 더욱 이해가 쉬울 것입니다. 문제를 요약하면, "..

0. 들어가며 우선 정수론이 뭘까요? 수학의 한 분야라는 건 알겠는데, 정수를 다루는 걸까? 맞습니다. 정수들의 여러 성질들에 대해서 연구하는 학문입니다. 깊이 들어가면 현대 수학에서는 해석적 정수론이나 대수적 정수론적인 방법론으로 접근해서 문제를 푸는 경우가 아주 많고, 그렇기에 저 두 분야에 대한 간략한 이해도 상당히 필요하지만 우선은 수학 글이 아니라 PS 글이니까 이건 넘기도록 하겠습니다. 정말 간단하게 정수론에서 다루는 문제의 예시를 들면, 다음과 같은 것들이 있습니다. 어떤 수를 어떻게 하면 소인수분해를 빠르게 할 수 있는가? 어떤 수가 소수인 걸 어떻게 빠르게 알 수 있는가? 어떤 방정식의 정수 해들을 어떻게 빠르게 구할 수 있는가? 정말로 재미 없는 수학문제들 같아 보이지만, 정수론은 의외..

제 모국어는 Python입니다. 0. 서론 PS를 한다면 KOI든 ICPC든, 그 외 다른 어떤 대회들이든 Python이 그렇게 권장되는 언어는 아닙니다. 당장(지금은 어떤지 모르겠지만 제가 KOI를 했을 때 기준으로)KOI는 Python을 아예 지원하지 않았고, ICPC도 올해 리저널에서야 처음으로 파이썬을 지원하기 시작했습니다. 그리고 그 모든 것을 뛰어넘는 결정적인 이유로는 Python이 C++에 비해 상당히 느리다는 점이겠네요. 아무리 최적화를 열심히 하고, Pypy를 쓴다고 한들, C++로 대강 짠 코드가 훨씬 더 빠르고, Python 코드는 시간을 꽉 채워서 겨우 맞거나 시간 초과(TLE)를 보는 경험은 Python으로 어느 정도 PS를 해보신 경험이 있으신 분들이라면 다들 있으실 겁니다. 이..

언제가 될지는, 애초에 개최가 가능할 정도로 검수진이 모일지는 미지수긴 하다마는, 제1회 은하콘을 개최하려고 합니다! 8-9문제 정도 다양한 난이도의 문제들을 대강 구상해놓았고, 제 이름을 당당히 걸 수 있는 대회 하나는 학부 졸업하기 전에 한번은 꼭 열어보고 싶다고 줄곧 생각해와서 결심하게 되었습니다! 다만 직접 개최는 처음 하는 경험이다 보니 주변 분들에게 이것저것 여쭈어 봐야할 것 같네요. 혹시 도움 주실 수 있는 분이 계신다면 감사히 받겠습니다.

11월 18일부터 19일까지 2022 ACM-ICPC 한국 리저널 겸 제 22회 전국 대학생 프로그래밍 경시대회를 치르고 왔습니다! 저는 MunSongSong Eggdrop(문송송 계란탁)팀으로 다른 후배 두 명과 참가했고,(스코어보드 기준)전체 7등, 교내 3등을 기록했습니다. 최종 스코어보드는 다음과 같습니다. 아래에서는 팀 구성부터 본선 당일까지의 타임라인을 죽 훑어볼 예정입니다. 0. 팀 구성 때는 바야흐로 2021년, 복학을 앞두고 있던 저는 ICPC 팀이 있었으면 좋겠다고 생각했습니다. 코드포스 오렌지(Eunha)에 solved 다이아 2를 자랑하지만, 대부분은 수학 문제를 푸는 능력으로 밀어 올린 것에 가깝고, 자료구조 등에는 무척 취약한, 그리고 무엇보다도 2년 휴학을 해서 아는 학교 사람..