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여년 전)에는 한국 소프트웨어 업계는 쉬운 일들이 대부분이었기에, 복잡하고 어려운 것들을 경시했다. 그러나 이제는 삼성 핸드폰이 대표적이듯이 복잡하고 어려운 것들을 해 나가는, 해야만 하는 시대가 왔다.  그렇기에 '기초적인' 지식들이 있어야 하고, 그러한 지식들이 있어야만 위에 쌓아 올려가며 어려운 문제들을 해결해 나갈 수 있다. 그 '기초적인' 지식이 무엇이냐..

1. 덧셈(뺄셈) number - number>>>1 - 2-1 list의 경우, 뺄셈은 불가능하지만 덧셈은 가능하다.>>>[1, 2, 3] + [1, 2, 3, 4, 5, 6][1, 2, 3, 1, 2, 3, 4, 5, 6] 2. 곱셈number * number >>>4 * 520 list * number>>> [0] * 5[0, 0, 0, 0, 0] - 주의할 점이 있는데, 다차원으로는 곱셈연산으로 생성하면 문제가 생긴다는 점이다.>>>l = [[0] * 5] * 2 >>>l [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] >>>l[0][0]=1 >>>l [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]의도한 점은 (0, 0)의 값만 1로 바꾸는 것이었는데, (1, 0)의 ..

독립(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 ?- 당연히 아니다. 오히려 정반대에 가깝다.- 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개 사건의 독립이 성립할 조건이다.다음과 ..

전 확률 공식(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..