-
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이란 스택 자료구조란 항상 한쪽 방향에서만 자료의 입력 및 출력이 가능한 형태의 선형 자료구조입니다. 책상 위에 책을 무더기로 쌓아놓은 상태를 생각하면 스택 구조를 이해하기 쉽습니다. 여러 개의 책이 쌓인 상태에서, 우리는 가장 위에 놓여져 있는 책만 쉽게 들어올릴 수 있으며, 가장 위에만 새롭게 책을 놓는 것이 쉽습니다. 물론 중간에 있는 위치에 책을 넣거나 빼는 것도 가능하지만, 이를 위해서는 그보다 위에 있는 책들을 들어야 하죠. 여기서 가장 위에 있는 책이라는 의미는, 책들이 쌓이기 시작했을 때...
-
다양한 생성함수와 그 응용 (2)
개요 본문은 아래의 포스트와 내용이 이어지며, 다음 포스트의 내용을 부가적인 설명 없이 서술한다. 다양한 생성함수와 그 응용 (1) 이번에는 생성함수를 어떻게 실제 PS 문제에 적용할 수 있는지 살펴본다. 다변수 생성함수 이항계수의 생성함수 이항계수 $\displaystyle \binom{n}{k}$의 OGF를 유도하자. 먼저, 이항계수와 같은 값을 가지는 함수 $f(n, k)$를 귀납적으로 정의하자. 다음은 이항계수의 일반적인 귀납적 정의이다: 다음을 만족하는 함수 $f : \mathbb{Z}_{\ge 0}^2 \rightarrow \mathbb{R}$은 모든 음이 아닌 정수 $n$, $k$에 대하여, $\displaystyle f(n, k) =...