-
Minimum Steiner Tree의 계산
서론 그래프 $G$와, 정점의 부분집합 $T$가 주어졌을 때, $T$를 모두 포함하는 Spanning Tree ($G$의 부분그래프 중, 정점과 간선 일부를 선택하여 만든 트리)를 $T$의 Steiner Tree라고 한다. 가중치가 주어진 방향 없는 그래프 $G$에 대해 간선 가중치 합이 가장 작은 Steiner Tree를 계산하는 문제는 일반적인 상황에서 NP-Hard임이 알려져있다. 이 게시글에서는, 해당 Steiner Tree를 계산하는 동적계획법을 다룬다. Naïve 편의상, 그래프의 $G = (V, E)$의 정점 개수를 $N$, 간선 개수를 $M$, 정점 부분집합 $T$의 크기를 $K$라고 하자. 가장 쉽게...
-
Stern-Brocot Tree를 활용한 수론적 함수의 합 계산
개요 정수론에서 주로 다루는 중요한 수론적 함수로는 약수 함수 $\sigma_k (n)$, 오일러 피 함수 $\phi (n)$, 뫼비우스 함수 $\mu (n)$ 등이 있다. 이러한 함수의 학문적 중요도는 이루 말할 수 없으며, 컴퓨터과학와 PS 분야에도 종종 등장할 정도로 다양하게 활용된다. 본 글은 수론적 함수의 대표인 약수 함수 $\sigma (n)$의 구간 합을 효율적으로 계산하는 알고리즘을 서술한다. 함수의 합을 기하적으로 해석한 후, 이를 Stern-Brocot Tree 자료구조로 계산한다. 이후, 이 알고리즘의 시간 복잡도가 $\tilde{O} \left( N^{1/3} \right)$로 아주 효율적임을 보인다....
-
세그먼트 트리의 응용
세그먼트 트리 세그먼트 트리는 수열에 다양한 구간 질의를 빠르게 온라인으로 처리할 수 있게 하는 자료구조이다. 만약 세그먼트 트리에 대해 접해본 적이 전혀 없다면, 네 편의 강의 #1, #2, #3, #4를 참조하라. 세그먼트 트리를 설명할 때에 가장 흔하게 쓰이는 연습문제는 다음과 같다. 문제 1 수열 $A[0], \cdots, A[N -1]$ 이 있다. 이 수열에 질의를 고속으로 처리해야 한다. 질의의 종류는 아래와 같다. 두 수 $i, k$ 가 입력으로 주어진다. 이 때, $A[i]$ 를 $k$만큼 증가시켜라. 두 수...
-
이동하기 4 (BOJ 18796)
이 글은 BOJ 18796 (이동하기 4)의 풀이를 다룹니다. 현재 이 문제의 solved.ac 티어는 루비 5입니다. 이 문제의 흥미로운 점은 지문이 거의 똑같은 문제가 무려 22티어나 낮은 브론즈 2라는 것입니다. 두 문제의 차이는 네 글자뿐이지만, 이는 x 방향으로 이동하는 비용이 x 좌표가 아니라 y 좌표에 의존하게 된다는 매우 치명적인 차이입니다. (물론 y 방향도 마찬가지입니다.) 60 +---+---+---+ +60-+60-+60-+ | | | | 10 90 80 70 20 +---+---+---+ +20-+20-+20-+ | | | | 10 90 80 70...
-
Analysis of the Naive Bayes Classifier with Spam Filtering and MNIST datasets
Abstract Naive Bayes Classifier를 이용하여 MNIST dataset와 email dataset을 학습하고, k-fold cross validation을 이용하여 학습된 모델의 분류성능을 분석해본다. Keywords Naive Bayes Classifier, K-Fold Cross Validation, Spam Filtering, MNIST Introduction Bayes’ theorem 베이즈 정리는 사전 확률로부터 사후 확률을 계산하는 조건부 확률에 대한 정리이다. 사건 A와 B가 있고, 사건 A가 일어났을 때 사건 B가 일어날 조건부 확률과 A가 일어날 확률, B가 일어날 확률만을 계산할 수 있을 때, 사건 B가 일어났을 때 사건 A가 일어날 조건부 확률은 다음과...