리유나의 항해일지

너무나도 감개무량하네요. 이걸 달 수 있을거라곤 전혀 생각 못하고 살았어요. 이 과정에서 편식하던 알고리즘들 이것저것 많이 먹게 되어서 좋았다고 생각해요. 다만 아직도 트리 같은 걸 너무나도 편식하는 것 같아서 조금 걱정이네요. 클래스 8 가는 길에 풀었던 문제들은 다음과 같습니다! 몇개 빼고 거의다 수학/기하학/게임이론 쪽이네요 ㅋㅋㅋ; 앞으로 두루두루 여러 분야의 문제들을 풀면서 연습해보겠습니다!

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를 해보신 경험이 있으신 분들이라면 다들 있으실 겁니다. 이..

이번 icpc 사진 올라온 거 주욱 보다가 되게 마음에 들게 나온 내 사진이 있어서 조금 기뻤다. 어디 메인으로 걸어놓아도 무난할 거 같은데, 고민 중...