본문 바로가기

전체 글

 (30)
Game Theory 1 : Grundy, Green Hakenbush, Red-Blue Hakenbush
LGCPC 2024 예선 D. 보안 점검 풀이 3가지 정도의 풀이가 있습니다. 1. DnC opt DnC opt의 아이디어를 이용합니다. 항상 답이 단조감소한다는 관찰을 할 수 있습니다.  DnC opt를 하듯이, DnC(int l, int r)에서 초기에 추가된 간선(쿼리로 추가되지 않은 간선)들 중 이 시점에서의 답에 관여하는 간선들의 vector S를 관리합니다. mid = (l + r) / 2에 대해서 시점이 mid일 때의 답을 구한 후, 이를 ans라고 합시다. (이 때의 답을 구할 때, S에 쿼리 번호 l ~ r 사이 간선 추가/중요도 증가/한계점 증가 쿼리를 반영하고, (|S|+r-l)log|S| 등 |S|와 r-l에 관한 시간복잡도로 구할 수 있도록 해야 합니다. 이는 DnC opt 과정에서 t=l, t=r일 때의 답을 구해놓고, 미리..
PMA Chapter 6 : The Riemann-Stieltjes Integral Definition. let [a, b] given interval, a partition P of [a, b] :finite set of a points x_0, x_1, ..., x_n where a = x_0 \delta_x_i = x_i - x_(i-1).suppose f : bounded real function defined on [a, b]. for each partition P of [a, b], M_i = sup f(x) (x_(i-1) U(P, f) = sigma M_i \delta_x_i, L(P, f) = sigma m_i \delta_x_iintegral a, b^ = inf U(P, f), integral a^, b = sup L(P, f) if same, then f is Ri..
PMA Chapter 5 : Differentiation 왠만해선 real function만 다룰 것이다. ## Derivative of Real function Definition. f가 [a, b]에서 정의된 real-valued function일 때, any x \in [a, b]에 대해 \phi(t) = (f(t) - f(x)) / (t-x) (a0 f'(x) 생각시 존재 안함. f(x) = x^2 sin(1/x) if x!=0, else 0으로 잡자. f' = 2x sin(1/x) - cos (1/x)이고, lim x->0 f'(x) 생각시 f'(0) = 0. 즉 이 함수에서 f는 all point x에서 differentiable(즉 f' 존재) 하지만, f'이 continuous하진 않다. (0에서 discontinuous) ## Mean valu..
PMA Chapter 4 : Continuity ## Limit of Functions Function의 Limit가 정의되어야 한다. Definition. X, Y가 metric space일 때, E \in X인 E에 대해, f maps E into Y이고 p가 E의 limit point라 할 때, x -> p일 때 f(x) -> q라고 쓰거나, 혹은 lim x->p f(x) = q라 하려면, 다음을 만족하는 q \in Y가 존재해야 한다. for all \epsilon > 0. Exist \delta > 0, 0 0 p f(x) != f(p)일 수도 있다. (조건상에서 0 ..
PMA Chapter 3 : Numerical Sequences and Series ## Convergent of Sequences 엡실론, 델타. {p_n} is sequence in a metric space X. {p_n} is converge if..there is a point p \in X, for every e > 0, exist int N such that n >= N -> d(p_n, p) {p_n} converges to p.. p is limit of {p_n}. p_n -> p으로 표기.(or lim n->inf p_n = p) not converge -> diverge. set of all {p_n} : range. Theorem. {p_n} is sequence in metric space X.(a) {p_n} converges to p \in X every ..
PMA Chapter 2 : Basic Topology 어려워진다. ## Finite, Countable set A, B에 대해 A의 원소 x마다 B의 원소 f(x)가 대응된다면 f를 function from A to B(or mapping of A into B)라 하고, A를 f의 domain(f is defined on A), f(x)를 values of f라 하며, set of all values of f는 range of f라 한다. f : A -> B에 대해 f(A) = B라면 f maps A onto B라 한다.(전사함수) for each y \in B에 대해 f^(-1) (y)가 원소가 한개 이하이면 f를 1-1 mapping이라 한다.(단사함수) 1-1 mapping of A onto B가 있다면 A와 B를 1-1 correspondence하다..
PMA Chapter 1 : The Real and Complex Number System ## ordered sets $S$가 set이고, S의 order은 relation이며,

티스토리툴바