본문 바로가기

전체 글

 (37)
[궁극의 웰노운 알고리즘] 1. FFT, NTT, online FFT, FWHT 음...최근 최대한 셋을 돌고 코포랑 앳코더를 돌아보고 있는데 자꾸 망치니까 정신상태가 안좋아지는 것 같아서 당분간은 셋을 도는 것에 주력하지 않고 웰노운 아닌 웰노운 알고리즘들을 배워보고자 한다. 뭔가 이론을 배우는 것 자체는 힐링되는 느낌이라 좋은 것 같다. 이제부터 배우는 족족 최대한 빠르게 "웰노운" 알고리즘들을 정리해서 올려볼 것이다. 만약 내가 블로그를 올리지 않는다면 독촉바란다. 아무튼, 이번에 다룰 대상은 일반적으로 두 다항식을 빠르게 곱하는 것으로 잘 알려져있는 FFT와 그 변형인 NTT, 온라인 FFT, FWHT에 대해 다룰 것이다. 1. FFT 해당 절에서는 이 문제를 해결하며, 이해하는 것을 목표로 두어도 괜찮을 것이다: 15576번: 큰 수 곱셈 (2) (acmicpc.net) 1..
JOI 2022 리뷰 다행히도 의지를 잃지 않고 두번째 셋을 쳤다. 첫 셋보다는 비교적 열정적으로 돈 것 같긴 하다. 뭐 근데 완전히 풀집중한건 아니고 그냥 적당한 고민속도로 문제를 푼거라서 다음에는 "더 열정적으로" 칠 필요성을 느꼈다. 아무튼, 셋 리뷰나 하겠다. 1. intercastellar (?) 어렵지 않다. 대충 2로 나뉠 수 있을만큼 나누고 투포인터로 처리하면 된다. 쿼리가 정렬되어있지 않았다면 구현량이 조금 늘어서 귀찮았을 것 같은데 다행히도 정렬되어있어 굉장히 짧게 코드를 짤 수 있다. 얻은 점수는 100점 2. self study 전형적인 유형의 파라메트릭 서치. 처음에 a>b인 모든 것들에서 a만을 써서 최대한 해보고, 이제 남은 것들을 b만을 써서 덮어낼 수 있는지 확인하는 문제를 로그번 풀면 해결된다..
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번 정점을 루트로 하는 서브트..

티스토리툴바