-
이항계수의 빠른 계산
서론 $\binom{N}{K}$ 는 $N$개의 구분이 되는 물체 중 $K$개를 고르는 가짓수이고, 이를 이항계수라고 부른다. 이항계수는 한 조합론적 상황에서 많이 사용된다. 이 $\binom{N}{K} = \dfrac{N!}{K!(N-K)!}$임이 잘 알려져 있다. 이 수를 소수가 아닌 임의의 수 $M$으로 나눈 나머지를 구하는 방법에 대해서 알아본다. Naive 이항계수를 $M$으로 나눈 나머지를 구하는 가장 쉬운 방법은 실제로 $N!$을 그냥 1부터 $N$까지의 모든 수를 곱하는 것으로 계산하는 것이다. 하지만 이럴 경우에 나눗셈이 잘 되지 않는다. 예를 들어서, $M=9$인 경우에는, $6! = 720$과 $7!=5040$을...
-
주어진 수들의 XOR 연산으로 만들 수 있는 수
주어진 수들의 XOR 연산으로 만들 수 있는 수 자연수의 집합 ${a_1, a_2, …, a_N}$ 이 주어집니다. 우리는 이 중 두 개의 원소를 골라 XOR한 결과를 집합에 추가할 수 있습니다. 이 때, 다음 문제들에 대해 생각해보겠습니다. 자연수 $b$가 주어질 때, 이 $b$가 집합의 원소가 될 수 있는지 판별하기. 이 집합에 들어갈 수 있는 원소의 최대 개수 구하기. 이 두 문제에 빠르게 답할 수 있는 방법을 알아보겠습니다. 우선, 첫번째로 어떤 수들이 집합에 추가 될 수 있는지 알아보겠습니다....
-
C++ STL 컨테이너의 메모리 사용량 (2)
지난 포스트 C++ STL 컨테이너의 메모리 사용량 (1)에서는 list, vector, deque의 내부 메모리 사용량을 분석하고, 어떤 식으로 구현되어있는지 추측해보았습니다. 이번 시간에는 priority_queue, set, map, unordered_map을 다루도록 하겠습니다. priority_queue 컨테이너 priority_queue 컨테이너는 다음과 같은 형태로 정의됩니다. template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue; T는 타입, Container는 내부적으로 사용할 컨테이너, Compare는 heap을 구축하는데 사용할 함수를 의미합니다. 기본적으로 priority_queue는 std::vector<T>를 이용하고, std::less를 통해 max heap을 만듭니다. priority_queue는 heapify 등을 통해서...
-
Heavy-Light Decomposition
서론 알고리즘 문제를 풀다 보면 많은 경우에 문제를 그래프 문제로 모델화할 수 있음을 보게 됩니다. 여러 요소들간의 관계가 주어지는 경우에는 각 요소를 정점으로, 관계를 간선으로 두는 방식의 모델화가 자주 사용되고, DP 문제는 대다수의 경우 DAG(Directed Acyclic Graph)의 형태로 각 상태가 이어지게 되므로 역시 그래프 문제의 일종으로 볼 수 있습니다. 그런데 특별한 제약 조건이 없는 그래프 문제의 경우 이 모델화에 성공하면 대체로 문제가 쉬워지거나, 전형적인 알고리즘을 요구하는 문제로 바뀌게 됩니다. 오히려 제약 조건이 추가된 형태일수록 그...
-
2018 ICPC world Finals C. Conquer the world와 Tree DP optimization
2018년 World Finals에서 어느 팀도 풀지 못했던 문제인 Conquer the world(https://www.acmicpc.net/problem/15691) 문제에 대한 풀이와 사용된 아이디어에 대해 간단히 소개한다. 문제 문제 자체는 굉장히 간단하다. edge마다 이동할 때 드는 cost가 있는 트리가 있고, vertex $i$에 현재 $X_i$명이 있으며 최종 상태에는 적어도 $Y_i$명이 있어야 할 때, 사용해야 하는 cost를 minimize하는 문제이다. Heavy-Light Decomposition 이미 상당히 유명해진 트릭인 heavy-light decomposition에 대해 먼저 간략히 설명하고 넘어갈 것이다. rooted tree에서 heavy edge란, vertex $v$의 자식들 중 가장 subtree의 크기가 큰(vertex...