보호되어 있는 글입니다.

https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 복잡한 구현 문제다. 문제 서술이 조금 빈약한 점이 있는데, 클러스터가 떨어질 때에는 무조건 아랫 면이 다른 클러스터와 닿아야 멈출 수 있다. 예를 들어 예제 3번을 보면 ㄱ자 클러스터가 떨어지는 와중에 오른쪽 면이 다른 클러스터와 닿는 경우가 생기는데, 이때는 멈추지 않는다. 이런 느낌이다. 따라서 다음의 생각을 가지고 해결하면 된다. 1. 모든 클러스터는 바닥과 연결되어 있어야 한다. BFS로 체크한다. 단..

https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 꽤 복잡한 BFS 문제다. BFS로 해결해야 한다는 건 알겠는데, 하루가 지날 때마다 BFS를 쓰면 $O(E) \sim 10^7$ 를 최대 ${150 \over 2} = 75$번 수행하고, 백조도 다시 BFS를 써야 하므로, 여기에 2를 곱해주면 된다. 그럼 대충 $10^8 \times \alpha$가 나오는데.. 이대로 하면 TLE가 뜰 것이다.. 따라서 조금 최적화..

Linear Independence Suppose $A$ is $m \times n$ matrix with $m < n$. Then there are nonzero solutions to $A\vec{x} = \vec{0}$. (more unknown than equations). There will be free variables. Given a set of vectors $v_1, ..., v_k$, we can think about linear combinations of these vectors, $c_1 v_1 + c_2 v_2 + \cdots + c_k v_k$. The vectors are linearly independent iff $c_1 v_1 + c_2 v_2 + \cdots + c_..

Solving Ax=b, Ux=c, and Rx=d Unlike last time, suppose we have a linear system that have non-zero right-hand-side. The case $b \neq 0$ is quite different from $b = 0$. Right hand side terms will be changed as we do elimination process on left hand side. Let's think we have a linear system like below : This whole system can be represented as an augmented matrix form $\left[A|\vec{b}\right]$ - whi..

Solving Ax=0 Suppose we have a square, invertible matrix $A$. It is supposed to have $n$ pivots in $n$ columns. But what if we have rectangular matrix that may not have full set of pivots? let's think about a rectangular matrix $A$ and a corresponding linear system $A\vec{x}=\vec{0}$. We can do Gaussian elimination on this matrix $A$ and get $U$. Since the third row is a sum of the first and sec..

Vector spaces A vector space is a space that satisfies two requirements : 1. $\vec{v}+\vec{w}$ and $c\vec{v}$ are in the space. 2. all combinations $c\vec{v} + d\vec{w}$ are in the space. So, a real vector space is a set of vectors together with rules for vector addition and multiplication by real numbers. Examples of three spaces 1. The inifinite-dimensional space $\mathbb{R}^\infty$ is a space..

Abstract Propose two model architrectures for computing continuous word vector (CBOW, Skip-Gram) Propose two modified NNLM model using binary tree Introduce new method to measure word similarity Show that newly introduced models can be trained on very large model (reduced time complexity) Previous Works 기존에 있었던 word vector 학습 모델은 크게 두 가지로 나눌 수 있었다. 1. SVD(Singular Value Decomposition) 기반 모델 LSD(..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 수 하나를 집어넣고 median값을 물어보는 query가 있을 때, 100000번의 query를 어떻게 0.1s(1e7번 내외의 iteration) 안에 처리할 것인가 하는 문제이다. query의 개수를 $N$이라고 하고$(N \leq 100000)$, 정수의 범위를 $M$이라고 하자. $(M \leq 20000)$ 처음에 떠올릴 수 있는 방법은 linked list로 수를 집어넣..