79brue의 PS 블로그

이번 멘토링 셋은 JOI 2020으로, 4시간 동안 5문제를 풀어야 했습니다. 전체적인 난이도는 예상했던 것보다는 할 만했던 것 같습니다. 시간대별로 상황을 서술하겠습니다. 3주가 2주보다 먼저 올라오는 이유는... 아직 2주 문제들을 구현해보지 못했기 때문입니다. #1. Just Long Neckties (0:00 ~ 0:06) 만약 $A$와 $B$가 모두 정해진다면, 둘 다 오름차순으로 정렬한 뒤 같은 순서에 있는 것끼리 matching하는 것이 최적임을 쉽게 보일 수 있습니다. 따라서 $A$에서 가장 큰 것을 빼고 나머지끼리 matching시켜 답을 구한 뒤에, $A$의 값을 하나씩 바꿔 주면서 multiset 등을 이용해 계속 가장 큰 값을 찾아내면 됩니다. Time Complexity: $O(N..

이번 주부터 국대 멘토링 교육이 시작되었습니다. 내신 준비로 시간이 충분하지 않아 일부 문제들은 풀이만 생각하고 구현을 아직 해 보지 않았는데, 시험이 끝나는 대로 구현해 볼 예정입니다. 제가 배정받은 문제 세트는 다음과 같습니다. #1. Trous de Loop (BOJ 18368) 조건을 만족하는 가장 긴 구간을 찾는 문제이므로 투 포인터를 이용합니다. 각 구간에서 자기 내부의 길이 $d$ 구간 중 구간 합이 최대인 것을 찾아야 하는데, 이 문제는 사실 누적합을 이용하면 투 포인터를 돌리면서 구간 내의 최댓값을 빠르게 찾는 문제가 되고, 이는 덱으로 해결 가능합니다. 따라서 문제가 쉽게 풀립니다. Time Complexity: $O(N)$ #2. Highway Modernization (BOJ 183..

PMCC는 수학동아에서 운영하는 수학 사이트인 폴리매스에서 개최하는 코딩 대회로, 2020년 8월에 1회 대회가 열렸고, 2021년 2월에 2회 대회가 열렸습니다. 2회 대회는 1회 대회 때보다 더욱 다양해진 실력의 코더들을 위해 Division 1과 2로 나눠서 운영되었습니다. 준비 과정에서 CMS 서버를 세팅해 주신 whqkrtk04님, 문제 출제를 도와 주신 azberjibiou, blackking26, gunwookim님, 그리고 촉박한 검수 기한에도 불구하고 검수에 힘써 주신 16silver, ainta, gs18115, messi, TAMREF님께 감사의 말씀을 전합니다. 아래는 풀이 ppt 파일입니다. 작성을 도와주신 azberjibiou님과 blackking26님께 다시 감사의 말씀을 전합..

KOI 2020 본선 문제는 다소 쉬웠지만 문제의 질은 보통 이상이었던 것 같습니다. 예선 난이도가 상당히 극단적이었기 때문에 본선이 어떻게 나올 지 도저히 감을 못 잡았는데, 나름대로 만족스러운 성적을 얻어 좋습니다. 대회 시작 전 대회 시작 전, 여유롭게 codeblocks abbreviation 몇 개를 추가하고 간단한 프로그램을 만들어 실행시켜 봤는데, 실행이 되지 않았습니다. 당황한 나머지 python을 써야 하는 건가 잠시 고민했는데, 옆 컴퓨터로 옮겨서 실행해도 마찬가지였습니다. 그때 누군가 는 비표준 헤더라 사용할 수 없다는 사실을 알려 주었고, 그 뒤로 이 대회에서는 STL 자료구조 등을 쓸 때마다 그때그때 필요한 헤더를 include 하게 되었습니다. 여러모로 불편했지만 bits/std..

문제들의 난이도가 작년보다 전체적으로 높았습니다. 1회차 문제부터 쉽지 않다고 느끼는 문제들이 등장했고, 2회차부터는 모든 문제를 푸는 것도 매우 힘들어졌습니다. 특히 2회차 문제에서부터 삼분 탐색과 이분 매칭이 나오는 것은 난이도에 상당한 변화가 생겼음을 의미합니다. 문제의 퀄리티도 작년에 비해 매우 높아졌습니다. 특히 3, 4, 5회차 문제들은 한 문제 한 문제가 깊은 고민을 해야 풀 수 있는 문제였던 만큼 매우 재밌었습니다. 연습 문제 1. 최대구간합 앞에서부터의 누적 합을 구해 주면서 답을 갱신해 나가면, $O(N)$에 풀 수 있습니다. 유명한 문제이므로 간단하게 설명했습니다. #include using namespace std; typedef long long ll; int n; ll arr[1..

안녕하세요. 블로그를 개설하게 된 79brue입니다. 블로그를 개설한 이유는 크게 두 가지가 있습니다. 먼저 제 생각과 아이디어를 정리할 수 있는 개인 메모장이 필요했고, 제가 알고 있는 지식을 여러분께 공유하기 위함입니다. 처음 코딩을 배울 때 혼자서 공부하기 힘들었던 기억이 납니다. 이 블로그를 통해 코딩을 처음 공부하는 꿈나무들이 조금이라도 도움을 받을 수 있었다면 좋겠습니다. 주요 포스팅 내용은 아래와 같습니다. 문제 풀이: BOJ나 기타 웹사이트의 문제를 푼 뒤, 문제를 푼 방법과 풀이를 올립니다. 알고리즘: 평소에 잘 알려져 있지 않거나, 중요한 알고리즘들을 정리합니다. 또 유명한 알고리즘이라도, 처음 배우는 사람이 쉽게 이해할 수 있도록 소개할 수 있습니다. 대회: KOI, NYPC 등의 큰..