-
# Dependency Injection과 Event Driven Design
필자는 개인 프로젝트인 Olive를 개발하면서 디자인 관점에서 일어나는 문제들에 대해 고민해보는 시간을 가졌습니다. Premiere Pro 의 보급형 레벨을 목표로 하는 현 프로젝트는 수 많은 뷰들이 존재하고, 여러개의 모델들, 이를테면 타임라인 모델, 드로잉 모델, 리소스 모델 등이 한 데 어우러져야만 모양이라도 내볼 수 있는 수준입니다. 지금까지 다양한 웹 어플리케이션들을 개발해왔지만, 대부분이 한 두개의 뷰(View)를 중심으로 한 두개의 핵심 모델만을 구현하는 정도의 레벨이었습니다. 나름 어느정도 수준의 프로그램들을 많이 개발해왔다고 생각했었지만, 지금의 시점에서 그 프로그램들을 생각해보면 여태까지의 필자의...
-
계산 복잡도 위계와 불리언 식
계산 복잡도 위계와 불리언 식 계산 이론은 전산학의 근간을 이루며, 컴퓨터를 사용하는 모든 학문의 수학적 분석에 있어서 중요한 역할을 한다. 계산 이론 분야의 $P = NP$ 난제는 컴퓨터 과학의 거의 모든 분야를 관통하는 중요한 문제이고. $P = NP$ 난제의 여러 중요한 실용적 의미와 그 악명높음은 이미 대중적으로도 잘 알려져 있다. 계산 이론의 내용은 전산학의 어떠한 부분을 다루더라도 만나게 되는 경우가 많지만, 대부분의 내용은 튜링 머신과 같은 복잡한 개념을 바탕으로 정의된다. 이러한 특징 때문에, 계산 이론의...
-
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가 너무 커질...