ComputerScience (48) 썸네일형 리스트형 NP complete 우선 NP complete를 이해하기 위해 필요한 용어들을 먼저 정의한다. Abstract problem $Q$란 instance set $I$ 와 solution set $S$사이의 binary relation 을 의한다. 예를 들어, 최단경로 문제의의 instance는 Graph와 두 개의 vertices 들로 이루어져 있을 수 있다. 여기서 우리는 solution이 yes or no 에 해당하는 Decision Problem에만 집중한다. Decision Problem의 예시는 다음과 같다. 최단경로 문제 중 k step 안에 vertex u에서 vertex v로 가는 경로가 존재하는지를 묻는 문제를 PATH라고 할 때, instance $i= $로 정의하며 , $PATH(i)=0 \; \text{.. Doob's Inequality Durrett 책을 일부 정리한 내용입니다. Theorem 4.4.1 If $X_n$ is a submartingale and $N$ is a stopping time with $P(N\leq k ) = 1$ then $$ E X_0 \leq EX_N \leq E X_k$$ Proof) $K_n= 1_{\{N\leq n-1\}}$ 이라고 할 때 $(K \cdot X )_n = \sum\limits^n_{m=1} 1_{\{N\leq m-1 \} }(X_m-X_{m-1}) = X_n - X_{N \wedge n}$ 따라서 $$ EX_k - EX_N = E ( K\cdot X)_k \leq E (K \cdot X)_0 = 0$$ 또한 $X_{N\wedge n}$이 submartingale이므로 $EX_0 = .. Martingale and Almost sure Convergence Durrett 책 일부를 정리한 내용입니다. $H_n$ is predictable sequence if $H_n \in \mathcal{F}_{n-1}$. Theorem 4.2.8 Let $X_n$ be a supermartingale. If $H_n \geq 0$ is predictable and each $H_n$ is bounded then $(H\cdot X)_n$ is a supermartingale. Proof \begin{align} E ( (H\cdot X)_{n+1} | \mathcal{F}_n) &= (H \cdot X)_n + E (H_{n+1} (X_{n+1}-X_n) | \mathcal{F}_n)\\ &= (H \cdot X)_n + H_{n+1} E((X_{n+1}-X_n)|\m.. Conditional Expectation Durrett 책 일부를 정리한 내용입니다. Example 1. If $X\in\mathcal{F}$ then $E(X|\mathcal{F})=X$ Theorem 4.1.12 If $\mathcal{F}\subset \mathcal{G}$ and $E(X \mathcal{G}] \in \mathcal{F}$ then $E[X|\mathcal{F}]=E[X|\mathcal{G}]$ Proof) 모든 $A\in \mathcal{F} \subset \mathcal{G}$에 대해 $\int_A X dP = \int_A E(X|\mathcal{G}) dP$이다. 왜냐하면 $A\in \mathcal{G}$이기 때문에 Example 1에 의해 $X=E(X|\mathcal{G})$이다. Q.E.D Theorem 4.1.. Poisson Convergence Durrett 책을 일부 정리한 내용입니다. 앞으로 증명에 있어서 유용하게 활용되는 lemma 두 개를 소개한다. Lemma 3.4.3 Let $z_1,\dots,z_n$ and $w_1,\dots,w_n$ be complex numbers of modulus $\leq \theta$. Then $$| \Pi^n_{m=1}z_m - \Pi^n_{m=1}w_m| \leq \theta^{n-1} \sum\limits^n_{m=1} |z_m - w_m|$$ Proof ) Induction을 활용해 증명한다. $| \Pi^n_{m=1}z_m - \Pi^n_{m=1}w_m| \leq |z_1 \Pi^n_{m=2}z_m - z_1 \Pi^n_{m=2}w_m| + |z_1 \Pi^n_{m=2}w_m - w_1 \Pi.. Matroid Theory Definition 1.1 (Walk) Given a graph $G$, a walk in $G$ is a finite sequence of edges of the form $v_0,v_1,...,v_m$ where $v_i$ is a vertex of $G$. If the edges in the walk is distinct, then it is a trail. If the vertices in the walk is distinct, then the trail is a path. (except $v_0 = v_m$) Definition 1.2 (Closed Path) If $v_0=v_m$ in a path, then it is a closed path which is know as a cycle De.. Dynammic Programming Memoization vs Tabulation memoization은 top-down이며 필요한 subprobelm 만 풀지만, function call로 인한 overhead 가 발생한다. Tabulation는 bottom-up이며, recursion 에 수반되는 overhead가 없다 DP 예시 피보나치 수열 동일한 피보나치 수를 2번 계산하지 않도록 한다. recursion 만으로 풀 경우 동일한 피보나치 수를 2번 이상 계산하는 경우가 생긴다. 따라서 계산한 값을 저장해 둔다. (Memoization) 피보나치의 경우 bottom up 방식으로 풀어도 된다(bottom up 도 dp) 이항 계수 : nCk nCk = n-1Ck + n-1Ck-1 Rod Cutting Problem rod의 길이와 .. [leetcode] 53. Maximum Subarray Maximum Subarray - LeetCode Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제설명 배열이 주어졌을 때 subarray 중에 최대 합을 구하는 문제이다. 풀이 1. 시간 복잡도 O(NlogN) 풀이 : Divide and Conque 배열의 가운데 원소를 중심으로 왼쪽 배열과 오른쪽 배열을 생각해보자. 이 때 생각해 볼 수 있는 maximum subarrya의 형태는 왼쪽 배열에만 있거나 오른쪽 배열에만 있.. 이전 1 2 3 4 ··· 6 다음