본문 바로가기

Algorithm

 (11)
KOI 2024 2차대회 문제풀이 1차대회가 IMO TST와 겹쳐서 응시하지 못한 관계로, 이번 2차대회 역시 응시하지 못했다. 백준에 올라와 있는 문제를 한번 풀어보았다. 초, 중, 고등부에서 서로 다른 문제는 7개였다. 중등부 2, 3, 4번(고등부 1, 2, 3번)은 모두 다소 ad hoc 한 문제로, 생각하고 나면 구현은 매우 간단해서 재미있었다. 다만 몇몇 문제는 풀이가 옳음을 증명하는 것이 상당히 어려웠고, 이 글에서도 대충만 서술을 할 것이다. 수학 올림피아드 문제처럼 상세하게 서술하는 것은 어렵고 읽는 사람도 직관적으로 이해하기 쉽지 않을 것 같다.보물 찾기 (초1)양의 정수 k에 대해서 $2k$번째에는 $S+k$를, $2k-1$번째에는 $S-k+1$을 조사한다. 따라서 짝수번째에 $R$을 조사하기 위해서는 $2(R-S)$..
멘토교육 4주차 (IOI 2016 Day 1) 후기 7월 6일 13시 1분부터 18시 1분까지 IOI 2016 Day 1을 돌았다. IOI 2016은 koosaga 님이 학생으로 출전하여 금메달을 따셨던 셋인데, koosaga 님의 Day 1 성적과 정확하게 똑같은 성적이 나왔다. koosaga 님의 후기와 점수판을 보니, Day 1은 변별이 별로 없어서, 금메달 상위권은 202점이나 205점도 있지만, 168점을 받아도 Day 2 결과에 따라 상이 결정되는 셋이었던 것 같다. 물론 이게 8년 전의 사람들의 실력이므로, 지금 같았으면 은메달 하위권 정도일지도 모른다. 멘토교육 4회 모두에서 금메달에 준하는 성적이 한 번도 나오지 않았고, 계속해서 은메달이 나왔지만, 앞으로의 집중 교육 기간 동안 노력하면 금메달 가능성도 있을 것이라고 생각한다.세 문제를 ..
멘토교육 3주차 (IOI 2018 Day 2) 후기 7월 4일 13~18시에 IOI 2018 Day 2를 돌았다. 성적은 역시 좋지 않게 나왔고, Github에 업로드된 점수판이 없어서 등수를 정확하게 확인은 못했지만 은메달 상위인 것 같다. IMO 국대 떨어진 것이 참 다행인 것 같다. IMO 국대 됐으면 둘다 별로 좋지 않은 메달을 받고 끝났을 거 같은데, IMO가 떨어졌으니 IOI에 집중을 해서 금메달까지 실력을 올릴 가능성이 조금이라도 있는 것 같다. 내년에 IMO에 도전해야 하므로, 내년에 IOI 참가 여부는 선택사항이라 하더라도 올해 정보 실력은 어느 정도 이상 끌어올려야만 내년에 집중할 수 있을 것이다.   대회 시작 후 20분 동안 문제를 모두 읽었다. doll은 조건을 만족하는 회로를 구성해야 해서 일반적이지 않고 어려울 거 같아서, hi..
멘토교육 2주차 (IOI 2023 Day 2) 후기 2주차 멘토교육으로는 6월 16일 13시부터 18시까지 IOI 2023 Day 2를 돌았다. 역시 성적은 좋지 않게 나왔지만 그래도 1주차보다는 향상된 것 같다. 하지만 Beech Tree 문제는 예전에 읽어본 적이 있고, 스코어보드를 보는 바람에 Overtaking 이 쉽다는 것을 알고 있는 상황이었음을 감안하면 여전히 금메달에서 상당히 떨어져 있다고 봐야 할 것이다.  나보다 앞서서 어린 나이에 IOI 최상위권을 하는 학생들이 있다. 중국에서는 내가 IOI 여름학교 처음반에 입교한 나이인 14살에 코드포스 LGM을 찍은 사람도 있다고 한다. 다른 학생들에 비해 실력이 상대적으로 매우 뒤떨어져 있음을 인정해야 한다. IMO는 여섯 번 출전한 사람도 있고 최근에는 국내에서도 세 번 연속 금메달을 받은 사..
멘토교육 1주차 (IOI 2023 Day 1) 후기 IMO TST에서 떨어지고 나자, 곧이어 IOI 멘토교육이 시작되었다. 국내 PS에서 압도적인 1위를 점유하고 계시는 koosaga님께 멘토링을 받게 되어 대단히 영광스럽게 생각한다. 선발고사를 꼴등을 했는데 가장 훌륭한 멘토가 배정된 것은, 현재 실력이 모자라는 만큼 3개월간 누구보다도 많이 성장하기를 바라는 단장님의 의도였을 것 같다.6월 8일 토요일 13시부터 18시까지 IOI 2023 Day 1 셋을 돌았다. 좋지 않은 결과가 나온 만큼, 앞으로 3개월간 누구보다도 많이 노력해서 IOI에서는 잘 할 수 있게 해야겠다. 후회 없이 IOI를 잘 마무리해야, 그 뒤로 8개월간 수학에 집중해서 내년에 IMO 대표에 도전할 수 있기 때문이다. IOI를 잘 치면 내년에는 IOI는 안 나가고 수학에만 집중할 ..
JOI 2018 풀이 2월 5일 08시부터 12시까지 JOI 2018 셋을 돌았다. 그런데 운이 좋게도 11시 27분에 올솔브를 하게 되어, 남은 30분 가량의 시간 동안은 풀이를 쓰면서 푼 문제들을 정리해 보고자 한다. 참고로 3번은 정해가 아닌데 뚫은 거일 가능성이 높으며, 시간복잡도 증명도 제대로 하지 않았으니 정확한 풀이를 원하는 사람은 믿지 않도록 한다. 1번: Stove 각 사람 $i(1\leq i\leq N-1)$가 방문할 때마다 난로를 1초 동안은 켜야 하므로, 적어도 1의 비용이 소모된다. 여기서 i+1번 사람이 방문할 때까지 난로를 켜 놓는지, 1초 후에 끄는지에 따라 비용이 달라진다. 전자의 경우에는 총 비용이 $T_{i+1}-T_i$이므로, 추가적으로 비용 $T_{i+1}-T_i-1$이 소모된다. 그런데..
BOJ 17441번: 파리채 만들기 미적분학에 나오는 Green의 정리에 대해 학습한 후, 이를 사용하는 알고리즘 문제가 있다고 해서 찾아서 풀어보았다. Green의 정리를 제대로 이해하고 있다면, 그걸 모르는 사람에게도 설명할 수 있어야 하므로, 독자가 Green의 정리를 모른다고 가정하고 글을 써보기로 했다. 문제 내용과 계산식 다각형 모양의 영역 R에 두 점 $P(x_1, y_1), Q(x_2, y_2)$가 있을 때, $PQ^2$의 기댓값을 구하는 문제이다. 연속적인 점의 위치에 대한 기댓값이므로 구하는 기댓값 E는 다음과 같이 적분으로 표현된다. 여기서 $dA_1=dx_1dy_1, dA_2=dx_2dy_2$ 이다. $$E=\left ( \iiiint_{P, Q\in R} dA_1 dA_2 \right )^{-1}\times\iiii..
BOJ 30513번: 하이퍼 삼각형 자르기 SASA Programming Contest 2023 Div. 1 (Arena #11)을 쳤다. 원래는 학교 작은 실험실 일정과 겹치고 아레나가 참가 범위가 아니어서 치지 않으려고 했다. 그러나 작은 실험실 행사가 예상보다 일찍 끝났는데 백준을 열어보니 대회창에 진행중인 대회가 보여서 갑자기 치고 싶어져서 쳤다. 15시~18시에 한 대회인데, 사실상 15시 20분에 문제풀이를 시작했다. 늦게 시작했고 아레나 참가범위가 아니어서 성적이 아무 의미 없으니, 재미로 어려운 문제들부터, 즉 H번(A번에서 N, Q 제한이 바뀐 조건)부터 B번까지의 역순으로 풀기로 했다. E번까지 풀고 나니 17시 25분 정도였고, 부모님께 전달받을 물건이 있어서 빨리 내려갔다 오니 17시 35분이었다. B, C, D는 쉬우므로 ..

티스토리툴바