-
Fixed-base Miller-Rabin
shjgkwo님이 작성하신 포스팅에서 Miller-Rabin Algorithm을 소개하고 있습니다. 마침 저희 팀이 WCTF에서 출제했던 문제 중에 Miller-Rabin에서 base가 고정되어있을 때 실제로는 합성수이나 소수로 판정되는 수를 쉽게 찾을 수 있다는 취약점을 이용하는 문제가 있었기에 이 부분을 설명드리려고 합니다. Miller-Rabin Algorithm shjgkwo님의 포스팅에도 정보가 있지만 다시 한 번 설명하고 가겠습니다. 독자가 기초적인 정수론에 대한 지식은 가지고 있다고 가정하고 진행하겠습니다. 보통 어떤 수 $N$이 소수인지 판별하기 위해서는 1부터 $N^{0.5}$까지의 모든 수로 나눠보는 알고리즘을 많이 사용 합니다. 이 알고리즘은 $N$이 그다지...
-
2019 SCPC Round 2 5번 풀이
문제 요약 $M \times M$ 격자판에 $N$ 개의 점이 찍혀 있다. 각 점에 대해서, 그 점은 왼쪽 아래로 하는 가장 큰 정사각형을 그리려 한다. 단, 정사각형은 $N$ 개의 점중 어떤 점이라도 내부에 포함시키면 안된다. 모든 점에 대해서 정사각형을 그릴 때, 모든 정사각형 변의 합을 구하시오. $2 \le M \le 10^9$, $1 \le N \le 500000$ 풀이 1. 먼저 2D Range Tree 를 써서 특정 직사각형 구간에 점의 개수를 $O(\log^2 N)$ 시간에 알 수 있다. 여기에...
-
# Dependency Injection과 Event Driven Design
필자는 개인 프로젝트인 Olive를 개발하면서 디자인 관점에서 일어나는 문제들에 대해 고민해보는 시간을 가졌습니다. Premiere Pro 의 보급형 레벨을 목표로 하는 현 프로젝트는 수 많은 뷰들이 존재하고, 여러개의 모델들, 이를테면 타임라인 모델, 드로잉 모델, 리소스 모델 등이 한 데 어우러져야만 모양이라도 내볼 수 있는 수준입니다. 지금까지 다양한 웹 어플리케이션들을 개발해왔지만, 대부분이 한 두개의 뷰(View)를 중심으로 한 두개의 핵심 모델만을 구현하는 정도의 레벨이었습니다. 나름 어느정도 수준의 프로그램들을 많이 개발해왔다고 생각했었지만, 지금의 시점에서 그 프로그램들을 생각해보면 여태까지의 필자의...
-
계산 복잡도 위계와 불리언 식
계산 복잡도 위계와 불리언 식 계산 이론은 전산학의 근간을 이루며, 컴퓨터를 사용하는 모든 학문의 수학적 분석에 있어서 중요한 역할을 한다. 계산 이론 분야의 $P = NP$ 난제는 컴퓨터 과학의 거의 모든 분야를 관통하는 중요한 문제이고. $P = NP$ 난제의 여러 중요한 실용적 의미와 그 악명높음은 이미 대중적으로도 잘 알려져 있다. 계산 이론의 내용은 전산학의 어떠한 부분을 다루더라도 만나게 되는 경우가 많지만, 대부분의 내용은 튜링 머신과 같은 복잡한 개념을 바탕으로 정의된다. 이러한 특징 때문에, 계산 이론의...
-
Prime Number
목차 1. 개요 2. 개념 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 학교 고급 알고리즘 시간에 Miller–Rabin Algorithm 에 대해서 공부하게 되었다. 매우 흥미로운 내용이 많았으며, 다른 사람들과 공유하면 좋겠다고 생각하여 소인수 분해 알고리즘 등의 다양한 알고리즘을 알게 된것을 포함하여 공유하고 싶어졌다. 이번 포스트에서는 그 알고리즘들의 구현과 실제 문제에 대해 어떻게 사용되는지 소개하고자 한다. 기본 지식 일단 최소한 Modulo Operation, 즉, 나머지 연산에 대해서 조금 설명할 필요가 있다. Mod 연산은...