본문 바로가기

전체 글

 (10)
KOI 2021 후기 0. 서론 KOI 2021을 봤다. 작년에는 전형료가 엄청나게 비싸진 것도 있고 IOI 일정과도 겹쳐서 응시를 안했다. 근데 끝나고 문제들을 들어보니 다 너무 쉽게 풀렸다. 쳤으면 400점이 나왔을 거 같아서 올해는 억울해서 응시를 했다. 딱히 준비를 하지는 않았지만 일단 목표는 올솔이었다. IOI를 기점으로 폼도 엄청나게 떨어지고 (IOI 후기도 빨리 써야겠다.) 공부도 안해서 가능할 리가 없었지만 아무튼 목표는 올솔이었다...ㅋㅋ 1. 시작 전 대회 시작 1시간 전에 줌 고사실로 입실해서 이것저것 검사를 받았다. 온라인으로 대회를 여러번 진행하더니 이제는 부정행위 감시도 굉장히 철저해지고 체계적이게 된 것 같았다. 이 부분은 참 좋았다. 다만 감독기기 (== 핸드폰)을 후면카메라로 바꿔서 들고 주변을..
2021 IOI 멘토 교육 일지 #3 이번 주는 총 5문제를 받아 모두 풀었다. 모두 적당한 난이도에 생각을 충분히 해볼 수 있는 문제들이었다고 생각한다. 밑의 풀이는 푼 순서대로 작성하였다. 최고인 대장장이 토르비욘 (#) 먼저 관찰할 수 있는 사실은 직사각형 중에 밑변의 길이가 같은 것이 없다면 그냥 순서대로 정렬해서 쌓으면 조건을 만족시킬 수 있다는 사실이다. 따라서 문제를 "정수 페어가 N개 들어올 때 중복되지 않게 각 페어에서 하나씩 숫자를 뽑아 그 합을 최소화하는 문제"로 변형할 수 있다. 여기서 정수 페어를 간선으로 생각하고 각 수를 정점으로 하여 그래프를 생각해보자. 이제 각 간선별로 양 끝점을 하나씩 배정해 주는 문제가 되는데, 컴포넌트 별로 분리해서 생각해도 무방하다. 만약 컴포넌트에 간선이 정점보다 많다면 이는 배정 불가..
2021 IOI 멘토 교육 일지 #2 이번 주에는 4문제를 받아서 4문제 모두 풀었다. 아는 문제들이 많이 보였지만 나름대로 생각도 해보고 구현도 해볼 수 있는 셋이었다. 이번 주차는 문제를 푼 순서대로 간단하게 풀이와 생각을 적어 보았다. 사무실 이전 (#) 우선 문제를 좀 더 단순하게 생각할 필요가 있다. 총합을 구하는 것이 목표이므로 문제를 "트리 위에 빨간점이 M개, 파란점이 K개 있을 때 서로 다른 색의 끝 점을 갖는 모든 경로의 길이 제곱의 합"과 같은 식으로 생각하도록 하자. 제곱이라는 조건이 생각하기 어려울 수도 있지만, 이는 (a+b)^2 = a^2 + b^2 + 2ab라는 간단한 식으로 해결해줄 수 있다. 경로들에 대한 문제이므로 센트로이드 디컴퍼지션을 해야겠다고 생각했다. 그럼 각 단계에서 센트로이드를 지나는 모든 경로를..
2021 IOI 멘토 교육 일지 #1 총 5문제를 받았고 읽어본 문제가 2문제 있었다. 아는 문제 + 쉬운 문제 하나로 총 3문제를 풀었으며 나머지 두 문제는 풀이 구상을 마치고 구현은 시간 상의 이유로 하지 못했다. 시험 기간 + 과제 + 졸업논문을 맞아서 어쩔 수가 없게 되었다. 순서대로 풀이와 문제에 대한 생각을 기록해보았다. Trous de loup (#) 판자가 없다면 간단한 투포인터 문제이다. 채울 구간을 결정한 뒤 판자를 덮는다고 생각하면 구간 내에서 가장 합이 큰 D개를 덮는 것이 최적이다. 누적합을 이용해 적절히 판자의 위치별 판자가 커버하는 양을 구해두면 구간의 최대값을 구하는 것이고 이는 덱을 이용해서 전체 시간복잡도 O(N)에 할 수 있다. 하지만 나는 처음에 생각을 편하게 하기 위해 파라메트릭으로 구간 길이를 결정하고..
꽃집, Parklife, 싼 비용 [주간 PS 리뷰 2020.4월 1-2주] 주간 PS 리뷰 지난 주에 이것저것 하다보니 (주로 롤이다) 한 주 PS 리뷰를 걸렀다. 2주 동안 좋은 문제를 많이 풀어서 정말 재미있었다. 그동안 명확하게 이해를 못했던 에일리언 트릭에 대해서 심도있게 이해를 하려고 노력했고 성공했다고 생각한다. 도대체 옛날에 잘못 짠 에일리언은 어떻게 맞았는지 1도 모르겠다. 그리고 가장 큰 수확으로 수열과 쿼리 33 (Honorable Mention)을 푼 것이 있겠다. 워낙 좋은 문제라 그런 것도 있고, 첫 루3이라 그런것도 있고, 2트에 맞아서도 매우 기분이 좋다. Utilitarianism https://www.acmicpc.net/problem/16191 트리에서 매칭 K개를 고를 때 최대 가중치 합을 구하면 된다. 이런 문제를 접근하는 좋은 방법으로는 M..
IOI 2008 [주간 PS 리뷰 2020.3월 4주] 주간 PS 리뷰 이번 한 주는 IOI 2008 문제 + 몇 개 풀면서 나름 알차게 푼 거 같다. 요즘 내신 수학과 PS를 격일로 하고 있는 이 정도 풀었으면 나쁘지 않다. 개인적으로 뿌듯하기도 하다. 다만 반성할 점은 블로그 글을 안 쓰고 넘어갈 뻔했다는 정도인 것 같다. 다음주는 oj.uz에 막 올라온 따끈따끈한 JOISC 2020을 풀어보려고 한다. IOI 2008https://www.acmicpc.net/category/detail/527IOI 2008을 아직 풀지 않은 pyramid base 빼고 묶어서 리뷰해보려고 한다. Type printer 주어진 단어들을 트라이로 만들고 한 번 순회하면 답이다. 그런데 마지막 리프에 도달한 후에는 다시 올라올 필요가 없으므로 총 연산 수는 마지막 단어의 길..
쿼리와 쿼리 [주간 PS 리뷰 2020.3월 3주] 주간 PS 리뷰 리뷰를 매주 쓰기로 하고 한 주만에 망해버렸다. 이번 한 주간 백준에서 푼 문제가 쿼리와 쿼리, 트쿼3 두 문제 뿐이다. 한 주간 한거라고는 유튜브보고 블로그 검색 밖에 없는 것 같다. 이번 주는 저 두 문제 리뷰로 마치고 문제를 열심히 풀어야겠다. 코포도 글로벌 라운드를 치기는 했는데 3문제 풀고 복통으로 탈주해서 -200을 먹은 라운드라 딱히 쓸 것도 없고 가만히 반성만 해야겠다. 그래도 PS 리뷰를 시작한 걸 다행이라고 생각한다. 주간 리뷰조차 안했으면 열심히 한 주간 쳐 놀아버린 것도 몰랐을 거 같다. 최근들어 PS에 대한 의욕이 예전 같지 않은 것 같다고 느꼈다. 그래도 며칠간 재미는 문제도 많이 보고 공부할것도 많이 생겼으니 초심으로 돌아가 좀 더 열심히 해봐야겠다. 잡설은 이..
timeismoney, Wild Boar [주간 PS 리뷰 2020.3월 1-2주] 주간 PS 리뷰 국대교육 멘토링 때 잠시 사용한 이후 버려진 블로그를 활용하기 위해 앞으로 매주 하나씩 내가 한 주간 풀었던 문제들의 리뷰를 작성할 계획이다. 내가 푼 문제를 정리하는 차원에서도 좋을 것 같고 뭔가 기록을 남긴다는 의미에서 세운 계획이다. 또, PS를 공부하는 사람들에게도 여러 문제들에 대해 참고할 자료를 남기면 좋을 것 같다는 생각이다. 설명 능력도 부족하고 아는 것도 많지는 않지만 노력해보려고 한다. 노력하다보면 언젠가는 구사과 블로그처럼 대단한 블로그가 될 수도 있지 않을까? 리뷰하는 문제는 그 주에 내가 푼 문제들이고, 그 중에서도 나름 의미가 있는 문제들을 추려서 작성할 계획이다. 글이 길어지거나 중요한 주제라고 생각되는 문제들은 리뷰에서 언급만 하고 따로 글을 쓸 수도 있을 것..

티스토리툴바