본문 바로가기

코딩/국대 멘토링 교육

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