-
동적 계획법을 최적화하는 9가지 방법 (Chapter 2)
동적 계획법을 최적화하는 9가지 방법 (Chapter 2) 이 글은 Chapter 1에서 계속된다. 4. Knuth’s Optimization Recurrence: $DP[i][j] = Min_{i \le k < j}(DP[i][k] + DP[k + 1][j] + C[i][j])$ Condition: $C[i][j]$ is a Monge array, and satisfies $C[a][d] \ge C[b][c]$ for $a \le b \le c \le d$. Naive Complexity: $O(n^3)$ Optimized Complexity: $O(n^2)$ Knuth Optimization은 어떠한 구간을 쪼개는 형태의 동적 계획법을 최적화한다. Optimal Binary Search Tree 라고 알려진 문제를 Knuth가 $O(n^2)$ 동적 계획법으로 해결할...
-
이항계수의 빠른 계산
서론 $\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)의 형태로 각 상태가 이어지게 되므로 역시 그래프 문제의 일종으로 볼 수 있습니다. 그런데 특별한 제약 조건이 없는 그래프 문제의 경우 이 모델화에 성공하면 대체로 문제가 쉬워지거나, 전형적인 알고리즘을 요구하는 문제로 바뀌게 됩니다. 오히려 제약 조건이 추가된 형태일수록 그...