리유나의 항해일지

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

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

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

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

https://www.acmicpc.net/problem/16993 16993번: 연속합과 쿼리 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j : Ai, Ai+1, ..., Aj에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N) 수열의 인덱스는 1부터 시작한다. 연속합은 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합이며, 수는 한 개 이상 선택해야 한다. www.acmicpc.net KOI 중등부 역대급 난이도로 유명한 웰노운....(동어반복인가??)이면서 다이아급 문제인 금광을 풀고 싶어서, 그앞의 연습문제 쯤 될법한 연속합과 쿼리를 풀러 갔습니다. 전반적으로 금광의 하위호환이다 싶었는데, 그래도 이게 ..