정보정보이론에서 정보란 예측 불가능한 정도를 나타내는 물리량이다.확률 $p$의 정보는 수식적으로 다음과 같이 정의된다.$$I(p) = -\log_2 (p)$$ 그래프로 나타내면 다음과 같다.즉, 확률이 1인 사건은 정보량이 0이고, 확률이 낮은 사건일수록 정보량이 크다. 이를 다음과 같이 생각해볼수도 있다.어떤 사건이 일어날 확률이 높다는 것은 그 사건을 예상하기 쉽다는 것이고, 예상과 일치한다는 것은 새로운 정보가 없다는것이니까 정보량도 낮다고 볼수 있다.  entropy어떤 확률변수 $X$에 대해 $X$의 엔트로피는 $X$의 정보량의 평균(기댓값)으로, 다음과 같이 정의된다.$$H(X=x) = - \sum p(x_i) \log_2 p(x_i)$$ 정보와 엔트로피의 단위는 $log$의 밑에 따라 다른데..

SGD (Stochastic gradient descent)$$w_{t+1} = w_{t} - \alpha \cdot \frac{\partial J(t)}{\partial w_{t}}$$ $\alpha$ : 학습률로 0.01, 0.001등의 작은 값을 사용한다. 가장 기본적인 형태의 optimizer로, (mini-)batch 단위로 경사하강법을 한다.기울기가 0이되면 업데이트가 일어나지 않는다는 문제점이 있다. Momentum$$m_{t+1} = \beta \cdot m_{t} + (1 - \beta) \cdot \frac{\partial J(w_{t})}{\partial w_{t}}$$$$w_{t+1} = w_{t} - \alpha \cdot m_{t+1}$$ $m$ : 기존의 기울기에 지수 가중 평..

IntroductionCNN은 이미지나 시계열 데이터를 처리하는데 특화된 신경망 구조이다. 한번 이미지 classification 문제를 일반적인 MLP로만 해결한다고 해보자.그러면 먼저 이미지의 각 픽셀들을 모두 펴서 하나의 벡터로 만들게 되고, 이를 FC(fully connected layer)에 넣서 계산한다. 이러한 방식은 픽셀간의 위치 관계(예를 들면 이미지에서 가까운 두 픽셀은 서로 멀리 떨어진 픽셀보다 더 관련이 많다)등을 무시하고, 파라미터 양도 매우 많아서 이미지를 학습하기에는 비효율적이다.반면, CNN은 이러한 픽셀들의 공간적 구조를 고려해 더 효율인 신경망이다. CNN에서 각 레이어의 역할은 다음과 같다. 1. Convolutional Layer (Conv)- 이 레이어 에서는 edg..

Introduction Mo's Algorithm은 구간 쿼리들을 적절한 순서로 배치해 쿼리들을 빠르게 계산하는 테크닉 입니다. 다만, 쿼리들의 순서가 바뀌다 보니, 업데이크 쿼리가 없을때만 사용 가능합니다. 이 알고리즘은 Sqrt Decomposition과 비슷한 개념이 쓰임으로, 이를 알고 보시면 좋습니다. Algorithm $s$와 $e$를 각 쿼리의 구간 시작부분과 끝 부분이라고 할 때, 쿼리들을 $(\frac{s}{\sqrt{N}}, e)$에 대한 사전순으로 정렬 ($N$은 전체 구간의 길이)하고 순서대로 쿼리들을 계산해주시면 됩니다. (단, 두개의 포인터로 구간의 시작과 끝을 이동시키는 방식으로 계산해야됩니다) (아래 코드를 보시면 쉽게 이해가 되실겁니다.) Time Complexity 1. ..

Introduction Sqrt Decomposition이란 구간을 $\sqrt{n}$개의 bucket으로 나눠 쿼리를 $O(\sqrt{n})$ 만에 처리하는 테크닉이다. 물론 세그먼트 트리를 이용하면 $O(\log{n}) $만에 구간 쿼리를 계산할 수 있지만, Sqrt Decomposition 은 Mo's Algorithm에 기반이 된다고 하니 배워보자. 코드 아래의 코드는 이 문제를 기준으로 작성되었다. #include #include #include using namespace std; const int MAX = 1000000001, MIN = 0; struct Ele { int min, max; }; int n, m, sqr; Ele arr[100001], bucket[400]; inline E..

Master Theorem을 이용하면 재귀적인 구조를 갖는 알고리즘의 시간복잡도를 간단하게 계산할 수 있다. 알고리즘이 시간복잡도 $T(n) = aT(\frac{n}{b}) + O(n^k)$ 으로 표현될때, $T(n)$ 은 다음과 같이 계산할 수 있다. $$ \begin{align} &1. \; a>b^k \quad \Rightarrow \quad T(n) = O(n^{log_{b}{a}})\\ &2. \; a=b^k \quad \Rightarrow \quad T(n) = O(n^k log n)\\ &3. \; a

Introduction 단절점이란 제거했을때 연결되어있던 그래프가 둘 이상으로 나눠지는 그래프를 말한다. 단절점을 가장 naive 하게 구하는 방법은 모든 정점에 대해 그 정점을 제거할 경우 connected component가 증가하는지를 탐색을 통해 확인하면 된다. 이 경우 시간복잡도는 $O(V^2)$ 가 된다. 하지만 단절점의 특징을 사용해서 탐색 한번으로 $O(V)$ 단절점을 구할 수 있다. 단절점 구하기 아래 그림을 보자. 위 그림은 root를 시작점으로 dfs를 도는 중간 과정을 나타낸다. 빨간색 정점 : 현재 보고있는 정점이다. 검은색 간선 : 바로 직전에 타고(?) 온 간선으로 root 쪽에서 왔다는것을 나타낸다. 보라색 정점 : root 쪽에서 이미 탐색을 완료한 정점이다. 파란색 덩어리..

Euler tour technique 이란 트리를 전위 탐색(부모 -> 자식)으로 넘버링 해서 트리를 관리하는 테크닉이다. 이러한 방식으로 트리를 관리하면 트리에서 임이의 서브트리에 대한 쿼리를 쉽게 처리할 수 있다. 트리에 전위 탐색으로 넘버링을 하고, 임의의 노드에 대해 생각해보다. 이 노드를 루트로 하는 서브트리 내에 속하는 모든 정점들은 인접하고 연속하게 넘버링이 되어있다는 것을 알 수 있다. 다음의 사진을 보자. (검정 : node number, 파랑 : 전위 탐색으로 넘버링 된 수) 여기서 2를 루트로 하는 서브트리 내의 모든 정점들에 대해 넘버링 된 수들을 나열해 보면 2, 3, 4, 5, 6 으로 연속한 것을 알 수 있다. 이러한 특성 때문에 오일러 투어 테크닉과 세그먼트 트리 같은 자료구..

Introduction monotone queue 란 deque 의 상태를 증가하거나 감소하도록 유지시켜 수열의 특정 구간에서 최대 또는 최소를 찾는 기법이다. 다음의 문제를 보자. http://boj.kr/11003 우리는 길이가 L 인 연속한 모든 구간들에 대해서 최솟값을 찾아줘야 한다. 물론 가장 naive한 방법으로는 세그먼트 트리를 이용한 방법이 있겠지만, monotone queue 테크닉을 사용하면 O(n)이라는 세그보다 (O(n log n)) 훨씬 빠른 속도로 문제를 풀 수 있다. 최솟값을 구하는 경우 i와 j는 i ar..