PS하는 깃털

이항게수와 관련된 PS를 하다가 범위가 큰 n과 범위가 큰 r에 대해서 nCr의 일의 자리 수를 구해야하는 일이 생겼다. 일반적인 콤비네이션 계산(O(n))을 하고 일의 자리수를 구하면 시간초과가 나서 다른 방법이 필요했다. 이 포스팅에서는 이와 관련된 내용을 적어보려고 한다. 1. 조합을 계산하는 일반적인 방법 가장 쉬운 방법으로는 정의식대로 n!, (n-r)!, r!을 모두 계산해주고 연산해주는 것이다. 하지만 n과 r이 조금만 커져도 계산 시간이 오래걸리고 PS에서는 정수형 범위나 심지어는 long long 범위까지 넘어갈 수 있기 때문에 좋지 않은 방법이다. int factorial(int n) { int output = 1; for(int i = 1; i >n>>p; k1 = p_digit(n,..

오늘은 크게 어렵진 않지만 그래도 생각해볼 가치가 있는 문제를 가져와보았다. 이 문제는 quant라는 곳에서 인터뷰 문제로 나온 적이 있다고 한다. One hundred people are in line to board a plane which has exactly 100 seats. Each passenger has a ticket assigning them to a specific seat, and the passengers board one at a time. The first person to board is drunk, picks a random seat, and sits in it. The remaining passengers board; if they find their assigned se..

n²개의 정삼각형으로 이루어진 정삼각형 격자에서 정삼각형의 개수는 어떻게 셀까? 이 포스팅에서는 이에 대한 일반화를 해보려고 한다. 먼저 이러한 문제는 점화식으로 접근하는 것이 쉬울 것 같다. 먼저 사용할 점화식을 정의해주자. a(n,k) = |한 변의 길이가 n인 정삼각형 격자에서 한 변의 길이가 k인 정삼각형의 개수| 자명하게 a(n,1) = n², a(n,n) = 1이다. 이제 a(n,k)에 대해서 생각해보자. a(n,k) 을 계산할 때 위 그림에서도 볼 수 있듯이 a(n-1,k)에 새로 추가되는 정삼각형들을 더해주면 된다. 그럼 새로 추가되는 정삼각형의 개수를 구해보자. 1) 큰 정삼각형과 변이 평행한 정삼각형 이 경우는 구하는 정삼각형은 보라색 정삼각형이므로, n-k+1개가 된다. 2) 큰 정삼..

아마 대부분의 사람들이 픽의 정리를 들어본 적이 없을 것이다. 우리나라 교과과정에도 없고 KMO에서도 전혀 나오지 않는 내용이기 때문이다. 최근에 학원에서 이 정리에 대해 짧게 배운 적이 있다. 학원에서 들었을 때 꽤 흥미롭고 재미있어 보여서 추가로 찾아보았다. 여기서는 그런 내용들을 정리할 것이다. 또 이와 관련된 문제를 만들었는데, 그것도 풀어볼 것이다. 픽의 정리 꼭짓점이 격자점인 다각형에서 다각형의 내부에 있는 격자점의 수를 I 라고 하고, 다각형의 선분 위에 있는 격자점의 개수를 B라 할 때, 다각형의 넓이는 S = I + B/2 -1 로 나타낼 수 있다. 이것이 무슨 의미인지 직관적으로 이해가 가진 않지만 격자점에서 여러 도형의 넓이를 구해보면 픽의 정리가 성립함을 알 수 있다. 그럼 이제 증..

몬즈의 정리(Monge's Theorem)는 KMO 2차에 자주 나오는 정리로 근축에 대해 배울 때 꼭 배워야히는 정리 중 하나이다. 여기서는 몬즈의 정리와 이와 관련된 재미있는 문제 몇 개를 풀어볼 것이다. 몬즈의 정리 : 세 원 A,B,C가 두 점에서 서로 교차할 때, 세 공통현은 한 점에서 만난다. ( 세 원의 근축들은 공점선이다.) 참고하면 좋은 사이트 : https://en.wikipedia.org/wiki/Power_center_(geometry) Power center (geometry) - Wikipedia From Wikipedia, the free encyclopedia For 3 circles, the intersection of the radical axes of each pair ..

아마 KMO를 공부했던 사람이라면 페르마 포인트(Fermat Point)나 스타이너 포인트(Steiner Point)에 대해 들어본 적이 있을 것이다. 이들 모두 주어진 임의의 점들에 대한 기하 중앙값(Geometric median)과 관련이 있다. 이 글에서는 이들의 증명과 가중치가 주어질 경우에 대해서는 어떻게 하는지에 대한 내용을 정리하려고 한다. 아직 일반적인 증명을 할 정도까지의 수준은 아니기 때문에 삼각형과 사각형에 대해서 다룰 것이다. 기하 중앙값(Geometric median)의 정의 : 유클리드 평면에서 주어진 샘플 점들에 대해, 각각의 점들까지의 거리의 합이 최소가 되도록 하는 점 출처 : https://en.wikipedia.org/wiki/Geometric_median Geometr..