-
Prime Number
목차 1. 개요 2. 개념 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 학교 고급 알고리즘 시간에 Miller–Rabin Algorithm 에 대해서 공부하게 되었다. 매우 흥미로운 내용이 많았으며, 다른 사람들과 공유하면 좋겠다고 생각하여 소인수 분해 알고리즘 등의 다양한 알고리즘을 알게 된것을 포함하여 공유하고 싶어졌다. 이번 포스트에서는 그 알고리즘들의 구현과 실제 문제에 대해 어떻게 사용되는지 소개하고자 한다. 기본 지식 일단 최소한 Modulo Operation, 즉, 나머지 연산에 대해서 조금 설명할 필요가 있다. Mod 연산은...
-
Matroid Intersection
Matroid Intersection Recall matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $ \mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다. $\phi \in \mathcal{I}$ $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$ $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인...
-
ACER: Sample Efficient Actor-Critic With Experience Replay
ACER: Sample Efficient Actor-Critic With Experience Replay 제목에서도 볼 수 있듯이, 딥마인드에서 나온 Sample Efficient Actor-Critic With Experience Replay 는 Actor-Critic method에 Experience Replay를 접목시켜 데이터 효율성을 높인 새로운 강화학습 알고리즘을 제안하는 논문입니다. A3C의 off-policy 버전이라고 생각하셔도 됩니다. 논문 내용을 요약하면 다음과 같습니다. Experience Replay를 도입해서 Sample efficiency를 향상시켰다. Experience Replay를 사용하기 위해 그래디언트 계산에 off-policy correction을 추가했다. Importance sampling을 사용할 것인데 그냥 사용하면 bounded 되지 않은 importance weight 값이 여러번 곱해져 variance가 너무 커질...
-
data science 기초
Data Science 의 기초 contents what is data science? ready to start analysis feature check outliers PCA linear regression conclusion what is data science? 데이터 과학이란? 이번 주제에서는 데이터 과학이라는 분야를 다뤄보고자 한다. 딥러닝이 현재 큰 인기와 관심이 주목된 가운데, 데이터과학의 중요도 또한 크게 중요해지고 있다. 데이터들이 중요한 이유는 무엇일까? AI(인공지능)는 learning 을 통해서 자신의 내부 computation을 견고하게 만들고, 그 learning은 다름이 아닌 data들의 집합을 통해서 이루어진다. 여러가지 예를 들 수 있겠지만 image classification 이라는...
-
알고리즘 문제 풀이 3
알고리즘 문제 풀이 3 최근에 푼 재미있는 문제들을 포스팅 해보겠습니다. BOJ 1066번 에이한수 각 자리수를 등차 수열을 이루는 연속한 수들끼리 묶어서 $A$ 개의 그룹으로 나눌 수 있으면 $A$-한수 라고 할때, $A$-한수 이고 $(A - 1)$-한수가 아니면서 각 자리수가 비내림차순인 $N$ 자리 자연수의 개수를 구하는 문제입니다. 다음과 같은 사실을 관찰해 봅시다. $A$-한 수 이고 $A < N$ 이면 $(A + 1)$-한 수이기도 하다. 위와 같은 사실이 성립하는 이유는 $A < N$ 이기 때문에 적어도 한 그룹에는...