mitdog의 기록장

배열이란: "같은 형태"의 데이터(자료형)가 "연속적"으로 붙어서 저장되어 있는 자료 구조.특징검색이 빠르다(여러 기법들 이용)탐색이 빠르다(O(1)만에 찾을 수 있음(컴퓨터 특성))삭제, 삽입이 느리다(연속된 메모리를 차지하는 특성상 그렇다)사이즈가 고정적이다4가지 형태의 배열(packed, sorted를 기준으로)packed : 사용하는 인덱스만 왼쪽으로 몰아놨다.sorted : 인덱스 순으로 값이 정렬되어 있다. (여기선 오름차순)Packed, Unsorted(가장 간단한 형태)index01234567value374102--- 가장 보편적으로 알고 있는 형태.여기에 추가로 값이 몇 개 저장되어있는지 세는 변수가 있다고 하자.counter(C)5Search : 하나 하나 처음부터 뒤져봐야 한다. O(..

확률 세기(Counting)결과들(Outcomes)을 세는 것만으로 확률을 구할 수 있다.표본 공간의 모든 결과가 동일한 확률일 때(All outcomes in $\Omega$ are equally likely)$\displaystyle P(A) = \frac{|A|}{|\Omega|}$ (기호: | . | = number(#) of elements in a set(사건 속 원소의 개수))모든 결과의 확률이 p로 일어난다.event A: 유한 개의 모든 사건이 동일하게 일어난다. (finite number of outcomes that are equally likely)세는 것의 원리(Counting Principle)분할 정복 접근(Divide-and-Conquer approach)각 회차 별로 나누어..

독립(Independence)어떤 두 사건이 독립이다사건 A, B가 독립이면 다음을 만족하는 것이다.$P(A\cap B) = P(A)P(B)$$P(A|B) = P(A)$ (event B가 일어난 것이, A에 영향이 없다)A, B가 Disjoint => A, B Independent ? (사건 A, B가 서로소이면 독립?)당연히 아니다. 오히려 정반대에 가깝다.pf) $P(A), P(B) > 0$ and each Disjoint $=> P(A\cap B) \ne P(A)P(B) >0$ 독립 성질을 만족하지 못한다.어떤 집단의 독립$A_1, ... A_n$이 전부 서로 독립이려면,==2개끼리, 3개끼리, 4개끼리, ... , n개끼리 "전부" 독립==인 경우여야 한다.예시는 3개 사건, 4개 사건의 독립이 ..