-
Breaking Python random module
서론 PlaidCTF 2021에서 Fake Medallion 이라는 문제가 나왔습니다. 문제를 푸는 과정은 다음과 같았습니다. Qubit 30개가 |0>, |1>, |+>, |-> 4개 중 하나의 state로 존재합니다. 각 qubit마다 여분의 빈 2개의 qubit이 주어지는데, quantum teleportation과 probabilistic quantum cloning을 통해서 이 stage를 통과할 수 있었습니다. (자세한 설명은 이 글의 주제가 아니라서 생략하겠습니다.) Qubit 30개를 초기화할 때 Python random 모듈의 random.getrandbits(30)을 사용합니다. 한 번 1번 stage를 성공하면 이 값들을 수많이 받아올 수 있습니다. 이 값들을 모은 뒤 다음 random.getrandbits(30)을...
-
Small To Large Merging
Small To Large Merging “작은거를 큰거에 합친다”, 이름만 들으면 무엇인지 유추가 잘 되지 않습니다. 하지만 알고리즘을 공부하는 사람이라면 한 번쯤은 간접적으로라도 접한적이 있을 것입니다. 바로 Union Find의 Union by size에서 시간복잡도를 보장하기 위해 쓰이기 때문입니다. 알고리즘에서 소개한대로 작은 집합을 큰 집합에 합친다면 한번의 Find 연산이 $O(\log N)$만큼 걸린다는 것이 증명되어 있습니다. 이 글에서는 Small to Large Merging을 소개하면서 왜 이런 시간복잡도가 보장되는지 알아보고, 응용되는 문제의 풀이를 설명하겠습니다. 간단한 문제를 하나 풀면서 시작하겠습니다. 무작위의 수가 1개씩...
-
CORDIC(Volder's Algorithm)
자주 있는 일은 아니지만, 살면서 적어도 한 번쯤은 삼각함수를 사용하는 코드를 작성해야 할 일이 있을 것입니다. C++의 math.h 헤더나 Python의 math 모듈같이, 대부분의 언어에서 삼각함수를 비롯한 여러 기능을 지원하는 수학 라이브러리가 기본으로 제공됩니다. >>> from math import * >>> sin(1) # usage of sin function in Python 0.8414709848078965 그런데, 주어진 각도가 $ \pi/6 $, $\pi/4$, $\pi/3$과 같이 딱 떨어지는 특수각이 아닐 때에도 컴퓨터는 어떻게 삼각함수의 값을 구할 수 있는 걸까요? 위 예시에서 $\sin 1$의 값은...
-
Integer Partition
개요 고등학교 교육과정의 확률과 통계 과목에서도 볼 수 있었던 자연수의 분할은 DP로 계산할 수 있어서 PS에서도 종종 등장하는 주제입니다. 이 글에서는 자연수 분할의 점화식과 빠르게 계산하는 방법, 그리고 문제풀이에서의 활용을 다룹니다. 자연수 $n$을 자연수 $k$개의 합으로 나타내는 방법의 수를 $P(n,k)$라고 합시다. 자연수 $n$을 분할하는 방법의 수를 $P(n)=\sum_{k=1}^{n}P(n,k)$이라 합시다. 예를 들어, 4를 분할하는 방법의 수는 위 그림처럼 5가지가 됩니다. $P(n,k)$를 $O(nk)$에 계산하는 방법 $P(n,k)$를 직접 구하는 간단한 공식은 알려져 있지 않고, 보통 점화식을 통해 계산합니다. 위...
-
Stack 자료구조와 실습
Stack Stack이란 스택 자료구조란 항상 한쪽 방향에서만 자료의 입력 및 출력이 가능한 형태의 선형 자료구조입니다. 책상 위에 책을 무더기로 쌓아놓은 상태를 생각하면 스택 구조를 이해하기 쉽습니다. 여러 개의 책이 쌓인 상태에서, 우리는 가장 위에 놓여져 있는 책만 쉽게 들어올릴 수 있으며, 가장 위에만 새롭게 책을 놓는 것이 쉽습니다. 물론 중간에 있는 위치에 책을 넣거나 빼는 것도 가능하지만, 이를 위해서는 그보다 위에 있는 책들을 들어야 하죠. 여기서 가장 위에 있는 책이라는 의미는, 책들이 쌓이기 시작했을 때...