전체 글 (30) 썸네일형 리스트형 1월 PS일지(1) (feat. [궁극의 웰노운 알고리즘] 12. Lagrange interpolation) 저번에 예고하였던 대로, 궁극의 웰노운 알고리즘도 작성할 겸 PS일지도 쓸 겸 글을 작성하게 되었다. 총 2개의 ARC와, 총 1개의 다3 수학문제를 풀었으며, 한 개의 요코하마 셋을 돌았다(이전에 내걸었던 공약에 비해 한 것이 많지 않아보인다면, 사실이다. 다만 지난주동안 바빴어서 어쩔 수 없었다.). 또한, 앞으로는 그냥 PS일지에다가 궁극의 웰노운 알고리즘을 작성할 예정이다. 암튼, 일단은 궁극의 웰노운 알고리즘부터 설명을 하겠다. 1. Lagrange Interpolation사실, 이 주제는 별로 언노운은 아니고 아마 많은 사람들이 알고 있는 테크닉일 것이라고 생각한다. 그냥 핵심부터 말하자면, d차 다항식은 점 d+1개가 주어질 시 유일하게 결정된다는 것이다. 해당 글에서는 Lagrange In.. [ROAD TO ULTIMATE MATHCHUNG] 2. Bus Stop https://www.acmicpc.net/problem/18570원래는 오늘 풀 문제가 있었는데 하루종일 자다보니까 시간이 많이 지나버려서 그냥 눈에띄는거 하나 잡아서 빠르게 쌀먹했다. 일단, 당연히 아무 버스가 도착하는 시간은 모든 버스를 통틀어서 최소 주기보단 작거나 같을 것이다. 이를 T라고 하자. 또한, 아무 버스가 도착하는 시간의 확률변수를 t라고 하자. P(t>=x)는, 모든 버스가 x분보다 빠르게 도착하지만 않으면 되기 때문에, \( \frac{\prod_{k=1}^n (a_k-x)}{\prod_{k=1}^n a_k}=f(x) \)와 같이 기술할 수 있다. f(x)를 미분하고 -1을 곱하면, 확률밀도함수 p(x)를 얻는다. 기댓값은 xp(x)를 x:0~T까지 적분한 값이라는 사실을 알 수.. [ROAD TO ULTIMATE MATHCHUNG] 3/2. Atcoder Regular Contest 104 https://atcoder.jp/contests/arc104/tasks Tasks - AtCoder Regular Contest 104AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp104번 콘테스트부터 하는 이유는, 최근의 앳코더 형식과 비슷하게 출제되기 시작한 시점이 104번 콘테스트부터이기 때문이다. A. 자명. B. (i,j)가 실제로 가능한지 판별하는 방향으로 한다. (i,j) 구간에서 A개수가 T개수와 같고, C개수가 G개수와 같다면 가능하다. 따라서 모든 i에 대해서, j를 증가시키며 문제를 풀 수 있다. C... [ROAD TO ULTIMATE MATHCHUNG] 1. Graph Counting https://www.acmicpc.net/problem/18453문제를 아주 간단히 요약하자면, 그래프 자체로는 완전매칭이 없는데, 간선을 아무거나 하나 추가하면 완전매칭이 생기는 non-isomorphic한 정점 \( 2n\)개의 그래프의 개수를 세는 것이다(\(n\le 500000\)). 한가지 중요한 정리를 사용한다:https://en.wikipedia.org/wiki/Tutte%E2%80%93Berge_formula Tutte–Berge formula - WikipediaFrom Wikipedia, the free encyclopedia Characterization of the size of a maximum matching in a graph In this graph, removing one.. [궁극의 웰노운 알고리즘] 11. Partition number, Euler's Pentagonal Theorem 저번 글에서 예고한 대로, 궁극의 웰노운 알고리즘을 작성한다. 사실 이 주제에 대해서는 굳이 글을 쓸 생각은 없었다만, 그래도 나름 알고있으면 아주 못써먹을 정도는 아닌 알고리즘이라고 생각되어 포스팅하는 것이 낫다는 결론에 이르렀으며, 무엇보다 문제를 풀다가 한 번 더 마주치게 된 알고리즘이라서 포스팅하게 되었다. 1. Introduction다음과 같은 문제를 생각하자: 정수 \( n \)이 주어진다. 당신은 \(P(n)\)(즉, \(n\)번째 분할수)을 출력해야 한다. 분할수에 대한 기초적인 이론은 중등 KMO 수준에서도 자주 다루기 때문에 이 문제가 그리 어렵지 않게 풀릴 것이라고 예상할 수도 있지만, 생각보다 이 문제는 빠른 시간 내에 해결하는 것이 쉽지 않다. 아, 참고로 분할수라는 것이 무엇인.. [ROAD TO ULTIMATE MATHCHUNG] 0. 궁극의 수학충이 되기 위한 길 때때로, PS에서 수학문제를 잘 푼다는 것은 엄청난 이득이 되는 경우가 있다. OI류에서는 비록 자구와 애드혹 문제가 많은 반면, ICPC류 대회에서는 입력이 상수개인 이상한 카운팅문제를 잘 푸는 능력이 매우 중요해지며, 꼭 그런 문제가 아니더라도 수학적인 사실을 테마로 하는 문제들이 많이 등장하게 된다. 분명, 이 글의 독자의 예상 반응중 하나로는, "필자는 어째서 쓴다고 했던 궁극의 웰노운 알고리즘을 유기한 채로 이런 글을 쓰는가?"와 같은 의문에 도달할 것이다. 그 이유로는 몇가지가 있는데, 설명하면 막상 설득력이 떨어지기 때문에 넘어가겠다. 중요한 것은 내가 궁극의 웰노운을 완전히 버린 것은 아니라는 점이며, 다만 수학을 주제로 한 포스팅이 조금 많아질 예정이다. 아무튼, 위와 같은 이유로 인해.. 2024 회고록 안녕하신가? 매우 오랜만에 글을 작성하게 된다. 궁극의 웰노운을 기다리는 사람이었다면(만약 존재한다면), 간만에 올라온 글이 해당 주제가 아닌 것에 대해 큰 안타까움을 표한다. 최근에는 충분한 수준의 웰노운을 적절히 공부했다고 생각하여서 새로운 알고리즘을 배우는 것보다는, 그냥 문제를 푸는 식으로 수행하고 있어서 이러한 글을 많이 올리지 않게 되었다고 생각한다. 다만, 아직 모르는 알고리즘이 있어서 데인 일이 최근에 있었기 때문에 아마 타 알고리즘들을 공부하는중에 아주 간간히 궁극의 웰노운을 작성하게 될 것 같긴 하다... 아무튼 각설하고, 이번 글에서는 2024년에 대한 회고를 해보고자 한다. 사실 작년에도 회고록을 쓸지말지 고민했었는데 귀찮아서 그냥 안썼었는데, 지금은 왠지 다른걸 하는게 더 귀찮고 .. [궁극의 웰노운 알고리즘] 10. Square Counting Technique 굉장히 오랜 시간이 지나고, 드디어 10번째? 맞나? 아무튼 글을 쓴다. 사실 이렇게 글을 올리는 시간이 늦어진 데에는 타당한 이유가 있는데, 그만큼 필자가 배울 수 있으면서 아주 웰노운은 아닌 아이디어들이 줄어들고 있다는 것이다... 솔직히 쓰라고 하면 쓸 수 있는 것들을 많긴 하지만 그동안 여러개의 주제를 하나로 묶어서 글을 올렸다보니 소재가 빨리 고갈되었다고 생각한다. 따라서 앞으로는 그냥 하나의 주제를 올리는 대신 조금 더 글을 작성하는 기간을 단축해볼까한다. 아무튼, 이번 글에서 다룰 테크닉은 사실 그 이름이 실제로 존재하는 테크닉은 아니고, 그냥 general idea중 하나로 생각할 수도 있다. 그러나 이 아이디어를 발상하지 못하는 이상 문제를 해결하기 극도로 어렵기 때문에 이렇게 정형화.. 이전 1 2 3 4 다음
