-
Knuth's Algorithm X
안녕하세요? 오늘은 Knuth’s Algorithm X에 대해 알아보도록 하겠습니다. Knuth’s Algorithm X는 기본적으로 Brute-Force 알고리즘의 일종이지만, 성능이 좋은 편에 속하고 그 과정이 상당히 아름답습니다. Knuth’s Algorithm X Knuth’s Algorithm X는 간단히 말해, 어떠한 집합의 exact cover를 찾는 알고리즘입니다. Exact cover란 무엇인지, 간단한 예시를 통해 살펴보도록 하겠습니다. 집합 X = {1, 2, 3, 4, 5, 6, 7}이 있고, 집합 X의 부분집합의 집합인 집합 S가 주어집니다. S = {A, B, C, D, E, F}라고 하고 각각을 다음과 같이...
-
Effective Modern C++ (2)
저번시간에 이어서 오늘은 예전에 Effective Modern C++ 을 공부하며 정리했던 내용들을 포스팅해볼까 합니다~ C++11/14 에서의 best practice 에 관한 내용으로서 최근 C++20 이 나오는 시점에서 이 또한 최신 내용은 아니긴 하지만 여전히 많은 부분들이 유효합니다. Chapter 4. 똑똑한 포인터 (Smart Pointer) 항목 18. 소유권 독점 자원의 관리에는 std::unique_ptr를 사용하라. 보통 smart pointer를 처음 접한 사람들은 std::shared_ptr만을 남용(?)하는 경향이 있다.그러나 std::shared_ptr이 매우 강력한 존재이긴 하지만 크게 2가지 측면에서 단점이 있다. 첫 번째는 overhead이다. 참조 계수를 관리하기...
-
Cactus graph realization of degree sequence
Degree sequence 그래프에서, Degree sequence란 undirected graph의 각 정점의 차수(degree)를 늘어놓은 수열을 말한다. Graph realization problem이란, 수열이 주어졌을 때 그 수열을 degree sequence로 갖는 그래프를 실제로 construct하는 문제를 말한다. 여기서 다루는 그래프는 self-loop나 multiedge가 존재하지 않는 simple graph이다. 어떤 Degree sequence가 주어졌을 때, 이를 만족하는 simple graph가 존재할 조건은 Erdos - Gallai theorem 으로 널리 알려져 있다. 정리 1 (Erdos - Gallai theorem). $d_1 \ge d_2 \ge … \ge d_n \ge 0$ 가 finite simple...
-
동적 계획법을 최적화하는 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$을...