codingfarm

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134#include using namespace std; class ListNode {public: int value; ListNode* pPrev, * pNext; ListNode() { ..

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include using namespace std; class VectorNode {public: int value, key;}; class Vector {public: int cnt, reserved; VectorNode *nodes; void Resize() { reserved *= 2; VectorNode *tmp = new VectorNode[reserved]; for (int i = 0; i = reserved) Resize(); nodes[cnt].key = key; no..

세그먼트 트리는 배열의 구간합을 더 효율적으로 구하기 위한 알고리즘이다. 가령 임의의 배열이 주어질때 위 배열에서 길이 n만큼의 구간을 다 구하는데 걸리는 시간 복잡도는 $O(n)$ 이다. 하지만 매번 구간의 합을 구할때마다 해당길이 만큼 계속해서 반복하는것은 시간낭비이다. 더 효율적인 방법은 없을까? 임의의 배열 S가 주어질때 S[i]는 arr[0] ~ arr[i] 에 있는 모든 원소들의 합과 같다. 만약 $a \sim b$까지의 구간에 있는 원소들의 합을 구해야 한다면? S[b]-S[a-1] 을 통해 구간의 합을 $O(1)$의 상수 시간만에 구할 수 있다. 하지만 이 방법은 배열 요소의 값이 변한다면 값을 수정하기가 굉장히 번거로워진다. 가령 a[i]의 값이 변한다면 S[i] 이후의 값들을 모두 수정..

$X$와 $Y$가 공간 $S$에서 $joint\;pmf\;f(x,y)$를 가진다. marginal pmf는 공간 $S_X$와 $S_Y$에서 각각 $f_X(x),\;f_Y(y)$이다. 사건(event)$A = \{X=x\},\;B=\{Y=y\},\;(x,y) \in S$일때 $A \cap B = \{X=x, Y=y\}$ 이다. 왜냐하면 $$P(A \cap B) = P(X=x,\;Y=y)=f(x,y)$$ 그리고 $$P(B)=P(Y=y) = f_Y(y)>0\;\;\;(since\;Y \in S_Y)$$ 일 경우 사건 $B$가 주어질때 사건 $A$의 조건부확률(Conditional Probability)는 $$P(A|B)=\dfrac{P(A \cap B)}{P(B)}=\dfrac{f(x,y)}{f_Y(y)}$$..