AgingCurve

Orthogonal Range Searching(직교 범위 탐색)은 2-Dimension(Linear Algebra Concept) Universe Set $U \times U$에서 n개의 distinct한 point들이 있다고 하자. lookup($x_1, x_2, y_1, y_2$)를 rectangle range$[x_1, x_2] \times [y_1, y_2]$ 에 속한 모든 point 를 return하는 operation으로 정의한다. 즉, lookup($x_1, x_2, y_1, y_2$)은 $x_1 \leq x \leq x_2$, $y_1 \leq y \leq y_2$ 를 만족하는 모든 point (x, y)를 return하는 operation이다.여기서 우리가 살펴볼 problem은 loo..

시간복잡도, 공간복잡도를 줄이는 순서로 알아보자. 문제에 대한 설명은 다음과 같다.물품의 수 $N$, 무게 한도 $K$가 주어지고, 각 물품의 무게와 가치가 주어짐. 한 줄에 배낭에 넣을 수 있는 물건들의 가치합 최대를 출력 GreedyGreedy하게 풀고싶지만, 당장 생각해봐도4 76 134 83 6...이 주어지면 무게/가치를 기준으로 판단해도 6 13만이 들어오게 되어 local solution에 갇히게 됨을 알 수 있다. 따라서 완전탐색을 수행해야함을 알 수 있다. Complete Search#include #include #include std::vector> knapsack; int N, K; int sol(int position, int room, int value) { i..

주어진 board에서 BFS를 수행하여 모든 노드를 탐색하는 반복횟수를 출력하는 문제임.BFS를 가정하여 각 노드에서 탐색 종료 조건을 node의 elem이 1인 경우로 바꾸면 가장 긴 path를 찾는 문제로 바꿀 수도 있다. 물론 나는 그냥 재귀함수를 사용하지 않고 풀이 함수 로직 하나를 두고 그 함수 내에서 이중 반복문을 통해 inner에서는 현재 위치를 기반으로 탐색 가능한 위치를 다음 세대 큐에 집어넣는 역할로, outer에서는 현재 탐색가능한 위치를 담은 큐를 다음세대 큐로 복사하는 역할로 반복횟수를 count하기만 한다.#include #include #include using namespace std;int dx[4] = {-1, 0, 0, 1};int dy[4] = {0, 1, -1, 0}..

$$x \in \{0,1\}^n, \quad n=10000$$$$x_j = 1(\text{word j appears in email})$$$x_j$ 는 단어 j가 메일에 나타나는지를 의미한다. generative model을 만들기 위해 $p(x|y), p(y)$가 필요하다. Naive Bayes에서는 $p(x|y)$가 주어진 class에서 개별 feature의 조건부 확률 곱인 $\prod^n_{j=1}p(x_j|y)$로 모델링된다. Naive Bayes 모델의 parameter는 아래와 같다.$$\phi_{j|y=1} =p(x_j =1|y=1)$$$$\phi_{j|y=0} =p(x_j =1|y=0)$$$$\phi_{y} =p(y=1)$$각 parameter를 MLE로 유도하면 아래와 같다.$$\phi..