본문 바로가기

분류 전체보기

(35)
COI 2017 리뷰 아주 오랫만에 블로그를 쓰는데 음...이유는 생략한다. 방학이 시작했고, 고1 여름방학 이래로 최초로 수올준비를 하지 않는 방학이 와서 ps와 수학공부에 온 초점을 맞출 생각이기 때문에, 이틀에 한번씩 셋을 돌고 업솔빙까지 완료하는 계획을 세웠다.(물론 이번 셋은 업솔빙을 전부 하진 못했다.) 아무튼, 이번에 돈 셋은 COI 2017(크로아티아 정올)이다. 생각보다 문제가 많이 매웠다. 또한 5시간짜리 셋이긴 하나, 깨어나자마자 비몽사몽한 상태에서 셋을 돌고 중간에 학원에 가야 했던 일, 생각보다 의지박약때문에 설렁설렁 친 것 때문에 그다지 부분점수도 안 긁고 성적이 딱히 좋지는 않다. 잡담은 이쯤까지 하고, 각 문제들에 대한 솔루션과 나의 접근에 대해 서술하겠다. 1. ili 일단 n,m 제한이 살벌해..
DLAS에 대해서 가끔, 어떤 문제를 정해의 방식대로 푸는 것보다 휴리스틱을 통해 푸는 것이 훨씬 직관적이고 간단한 경우가 있다. 그러한 문제들은 내가 적절히 포스팅을 해두었기 때문에 참조하면 좋을 것이다. 휴리스틱의 종류에는 여러가지가 있다고 할 수 있는데, 대표적으로 Simulated Annealing과 Diversified Late Acceptance Search가 있다. 전자는 대체로 SA라고 부르며, 일반적으로 휴리스틱중에선 널리 알려진 편에 속하는 것 같다. 그러나, 본 포스팅에서 소개할 기법인 DLAS는 일반적으로 SA보다도 더욱 강력한 효과를 발휘하는 것으로 알려져 있다. DLAS의 정확한 이론과 작동원리, 증명에 대해서는 지식이 부족해서 설명할 수 없지만, DLAS가 어떠한 방식으로 작동하는지는 설명이 가..
구데기컵 X solved.ac 콜라보카페?후기 우선, 사진 자료가 많지 않다는 점에 양해 바란다. 평상시 사진을 찍는 것에 익숙치 않아서 어쩔 수 없었다. 일요일에 기숙사로 돌아가야 하는 특성상 넉넉하게 4월 1일에만 방문하였다. ~12:35 codeTon round 4를 쳤다. A,B는 그냥 풀었고, C랑 D가 뭔가 수학틱한 느낌이 강해서 풀고 E부터는 다음 날의 기상을 위해서 안풀고 그냥 침대에 누웠던 것 같다. 12:35~2:30 정후(mjhmjh1104)가 Ton 16개 받기를 간절히 원하는 모습을 구경했다. 이후 인터넷이나 유튜브를 조금 보았다. 2:30~9:00 잠을 잤다. 정확히 어떤 꿈을 꿨는지는 기억이 안나지만 아마도 학교의 일상과 관련된 꿈이었을 확률이 높다. 9:00~9:30 아침을 먹었다. 내 기억상으로는 이삭 토스트?를 먹었던..
2019 APMO 풀이 2019년 APMO 문제들에 대한 풀이이다. 사실 2012 SL 풀이 작성이 귀찮아서 새로 문제를 찾아보고 있는거지만...애초에 어떤 셋의 모든 문제가 올라오기를 기대하기보다는 정기적으로 재밌는 문제가 올라온다고 생각하는게 나을 것이다.(계속 작성중) 1. 다음 조건을 만족하는 $$f:\mathbb{Z}^+\to \mathbb{Z}^+$$를 구하여라:$$f(a)+b|a^2+f(a)f(b)$$ 더보기 우선, 소수에 대한 함숫값을 먼저 분석하자. P(n,n):f(n)+n|n(n-f(n))인데, n에 소수를 넣고 나면 f(p)+p|p-f(p)라는 사실을 알 수 있고, 여기서 p=f(p)라는 사실을 얻는다. 이제 P(p,b)를 보면 p+b|b^2-bf(b)인데, p를 키울 수 있는데에 반해 우항은 고정되어있기 ..
2012 IMO SL 풀이 2012 IMO Shortlist의 풀이이다. 앞으로 각 연도의 것들에 대한 해설을 작성할 것인데...아마 대부분은 IMO 공식 홈페이지에 있는 솔루션들을 번역한 것이 될 것이다. International Mathematical Olympiad (imo-official.org) 참조. 다만, 내 풀이가 존재하는 경우도 있을 것이며 대부분의 문제에서 찾을 수 있는 포인트등을 정리할 것이다. 아마 수학을 공부하고자 하지만 영어로 된 오피셜 솔루션에 가로막히는 경우 요긴하게 쓸 수 있지 않을까 싶다.(계속 작성중. 풀이가 추가되는 순서는 내맘대로다.) A1. 다음 조건을 만족하는 함수 f를 구하여라. $$f:Z\to Z, f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a..
백준 27092 - 생물 연구 문제를 요약하자면, 크기가 2 이상이면서 동일한 높이이며, 최소 공통 조상이 전부 동일한 정점의 집합의 개수를 세는 것이다. 정해를 읽어봤는데 생각과는 달라서 작성하게 되었다. 우선, 제곱 풀이를 생각해볼 수 있다. tree dp를 돌리면서, 어떤 서브트리의 루트를 최소 공통 조상으로 하는 집합의 개수를 세는 것이다. 만약 각 서브트리가 특정한 깊이를 가진 정점의 개수를 들고 있다면, 한 서브트리에서 문제의 답에 더해주어야 할 것은 각 높이에 대해, 각 서브트리가 가진 정점의 개수를 전부 곱한 값(그 높이의 정점이 존재하는 서브트리가 2개 이상인 경우에 한하여)을 전부 더해주면 된다는 사실을 직관적으로 알 수 있다. 다음과 같은 경우에, 1번 정점을 기준으로 카운팅해보자. 2번 정점을 루트로 하는 서브트..
백준 7936 - N의 존재 7936번: N의 존재 (acmicpc.net) 문제 자체가 워낙 간결해서 굳이 문제를 요약할 필요는 없을 것 같다. 우선, 정수론적인 사전지식이 몇가지 필요하다. 원시근과 이산로그에 대해 알고 있다면 해당 문제의 풀이를 이해하는데에 지장이 없을 것이다. 만약 p에 대한 원시근을 하나 찾는다면 문제가 해결되었다고도 할 수 있다. n을 p씩 올리는 행동을 n^m 항에는 어떤 영행도 미치지 않지만, n^n항에서는 지수가 정확히 1 늘어난 효과를 보여준다. 따라서 원시근을 일단 찾고 나면, n^n === a-n^m(mod p)인 문제를 해결하게 된다. 이때 n을 p씩 늘린다고 하였기 때문에, 그 원시근을 거듭해서 곱해주는 효과가 나타난다. 이 방법을 통해 특정한 값에 도달할 수 있는가는 이산로그 문제를 해결함..
백준 19702 - 친구 문제를 요약하자면, 자신의 양 옆에 친한 학생들만이 존재하도록 원탁에 학생들을 배치할 수 있는 방법을 출력하라는 것이다. 해당 사진에는 나와있지 않지만, 직접 링크를 타고 들어가보면 친한 학생들의 명수에 대한 조건이 주어진다. 19702번: 친구 (acmicpc.net) 19702번: 친구 선린인터넷고등학교에는 $N$명의 학생들이 있다. $N$명의 학생들 가운데 일부는 서로를 좋아한다. 신기한 사실이 있는데, 학생들 간에 일방적으로 좋아하는 경우는 없고, 반드시 서로 좋아하거나 www.acmicpc.net 이 문제는 조합론적으로 어떤 아이디어를 잘 적용해서 풀 수 있는 문제이지만, 본 글에서는 조금 다른 방법을 설명하고자 하는데, 바로 dlas를 사용하는 것이다. dlas같은 경우에는 이전의 squid ..