-
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가 일어날 조건부 확률은 다음과...
-
알고리즘 문제 접근 과정 8
알고리즘 문제 접근 과정 8 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 버스 노선 - KOI 2014 고등부 2번 풀이 이 문제를 해결하는데 큰 어려움이 되는 부분은 구간이 원형으로 되어있다는 점일 것입니다. 그렇다면 일단, 문제가 원형으로 생겨있지 않고 0번을 기준으로 일직선으로 생긴 형태라면 어떻게 해결할...