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개 사건의 독립이 ..

우리는 코드를 치고 실행하며, 그 실행 결과를 본다.그 코드에는 변수, 포인터, 연산 등 다양한 것들이 있다.그렇다면 도대체 '실행하면'이라는 과정에서는 무엇이 일어나고 어떻게 동작하는가?그것에 대한 답이 되겠다. (러프하게)CPU, BUS, Memory, Variable and Pointer참고 CPU: https://namu.wiki/w/%EB%AA%A8%EC%8A%A4%20%ED%85%8C%ED%81%AC%EB%86%80%EB%A1%9C%EC%A7%80%206502?rev=70기본적으로 컴퓨터는 '계산해서 적는다.'가장 간단하게 말하자면 저게 전부이다.좀더 디테일하게 적어보자면'메모리로부터 꺼내서 (BUS를 통해 전달하고) CPU에서 계산하고 메모리에 적는다.'이다.우리는 전자회로를 만들진 못하더라..

참고 자료:https://namu.wiki/w/%EC%A0%95%EC%A7%80%20%EB%AC%B8%EC%A0%9C원본 튜링의 정지 문제 증명은 튜링 머신과 대각선 논법을 통해 증명하나,러프하게 재귀와 소스 코드 만으로도 할 수 있다.어떤 프로그램과 입력 값을 인자로 받아 입력에 대한 프로그램의 동작이 무한한지, 멈추는지판별이 가능한 프로그램 D가 있다고 하자. (귀류)$$D(M, X) = {YES, NO} (M=Program, X=input)$$멈추면(끝나는게 가능하면) YES, 무한히 돌아가면 NO그러면 D의 출력과 반대로 출력을 하는 프로그램도 가능할 것이다.$$D'(M,X) = {NO, YES}$$D가 YES일 때, D'은 NO, D가 NO일 때 D'은 YES인 프로그램 D'은 당연히 가능하다...

컴퓨터공학부 교수님의 일화(약 10년 전)생물학 교수: 아니 컴퓨터공학이 왜 대학에 있는겁니까교수님: ?????? 미국 대학에도 다 있는데요????생물학 교수: 컴공 그거 밖에서 6개월 학원 다닌거랑 다를게 없다는데요, 대학에 있을 필요가 있나요교수님: 하하 뭐 그렇긴 하죠...교수님: (속으로) '그러게 뭐가 문제일까..'   이렇듯 옛날(10여년 전)에는 한국 소프트웨어 업계는 쉬운 일들이 대부분이었기에, 복잡하고 어려운 것들을 경시했다. 그러나 이제는 삼성 핸드폰이 대표적이듯이 복잡하고 어려운 것들을 해 나가는, 해야만 하는 시대가 왔다.  그렇기에 '기초적인' 지식들이 있어야 하고, 그러한 지식들이 있어야만 위에 쌓아 올려가며 어려운 문제들을 해결해 나갈 수 있다. 그 '기초적인' 지식이 무엇이냐..

전 확률 공식(Total Probability Theorem)$A_1, ... A_n$이 $\Omega$의 분할(Partition)이고, $P(A_i) > 0, \forall i$라고 하자.그러면 다음이 성립한다.$$P(B) = P(A_1)P(B|A_1)+P(A_2)P(B|A_2)+...+P(A_n)P(B|A_n)$$증명은 다음과 같다. 위의 가정과 공리 2번을 사용한다.그림으로는 이런 식이다. (최소 그림이라도 기억하라)Example 1)1 대 1 토너먼트. 팀 유형에는 3가지 타입(공격적, 수비적, 균형적)이 있다.vs Type-1 승률: 0.3vs Type-2 승률: 0.4vs Type-3 승률: 0.5전체 팀들의 타입 비율은 다음과 같다.Type-1 : Type-2 : Type-3 = 2 : 1 ..

개념과 표기- P(A|B), P(B) > 0- B가 주어졌을 때, A의 조건부 확률(conditional probability of A given B)라고 읽는다.- 직관적으로, 표본 공간(Sample space)이 B로 바뀌었다는 느낌. 정의- P(A|B) = P(A∩B)/P(B) , givenP(B) > 0- B가 일어났을 때, A였을 결과값. 확률 공리를 적용해보자(Checking the probability axioms)i) P(A|B) ≥ 0, ∀A ⊆ Ω 임은 자명하다.ii) P(Ω|B) = P(Ω∩B)/P(B) = P(B)/P(B) = 1 정규화도 당연하게도 만족한다.iii) A와 C라는 disjoint한 두 사건이 있다고 하자. 따라서, A ∩ C = ϕ 이면, P(A|B) + P(C..

확률 모델(Probabilistic Models): 어떠한 상황을 가정하여 확률을 따지기 위한 것. 다음의 2가지로 이루어진다.1. 표본 공간(Sample Space, Ω): 일어날 수 있는 모든 경우의 수가 전부 원소인 집합.ex) a coin toss : Ω= {H, T}ex) 2 coin toss : Ω = {HH, HT, TH, TT}사건(Event) : 표본 공간의 부분 집합이다. 특정한 조건 하의 원소들이다.ex) 2번의 동전 던지기에서 앞면이 한번이라도 나올 경우 A = {HH, HT, TH}표본 공간(Sample Space)의 조건원소들 끼리 서로 동시에 일어날 수 없어(mutually exclusive)야 한다. (unique outcome)모든 결과(경우)가 포함되어야 한다. (Coll..

어떤 것들을 '모아놓은' 것(Collection of Objects)집합의 포함된 x, 미포함된 x, 공집합의 기호유한 집합 VS 무한 집합(Finite or Infinite): 원소의 개수 기준으로, 유한한 개수냐 무한한 개수냐셀 수 있는 집합(가부번) VS 셀 수 없는 집합(Countable or UnCountable): 무한 집합인데, 셀 수가 있느냐 없느냐. 즉, 원소가 자연수 집합과 일대일 대응이 되는가?Countable : N(자연수), Z(정수), Q(유리수)..Uncountable : R(실수), I(무리수), S = {x : 0 ≤ x ≤ 1} 와 같이 연속된 구간..전체 집합(Ω, Universal Set) = Sample Space: 모든 경우의 수를 포함한 집합, n차원 공간의 모든..