Grammer 1. It was difficult in the beginning, but she got used (?) it. Ans: to -> 간단한 문제, 핵심은 be used to에서 be 대신 get을 쓸 수도 있다는 것. 또한 익숙하다, 적응하다의 뜻으로 쓸 때는 be used to 뒤에 명사임. 2. Don't worry. It will be done (?) you know it. Ans: before -> 해석 문제, 알아채기도 전에 끝날 것이라는 뜻이 되야함. 핵심은 시간의 부사절에서는 현재시제 know가 미래의 뜻을 포함한다는 것. 치과치료 받는 상황인 듯. 3. Actually, he was in the back, (?) the whole way. Opt: a) slept b) Sle..

1. Introduction 두 확률 변수의 사전 확률과 사후 확률 사이의 관계를 나타내는 정리이다. 조건부 확률 $P(A|B)$를 알고 싶은데, 가지고 있는 정보가 $P(A), P(B), P(B|A)$일 때, 이를 통해 알아내는 정리이다. 2. Approach 유도는 어렵지 않다. 이전의 조건부 확률의 확장이다. $$P(A|B) = {P(A\cap B)\over P(B)} = {P(B|A)P(A)\over P(B)} = {P(B|A)P(A)\over P(B|A)P(A)+P(B|A^c)P(A^c)}$$ 여기서, $P(A|B)$는 사후확률 (Posterior Probability)로 구하고자 하는 사건(B가 일어났을 때 A)의 확률이다. $P(A)$는 사전확률 (Prior Probability)로 B가 일..

1. Introduction 조건부 확률은 사건 B가 일어나는 경우에 사건 A가 일어날 확률을 말한다. 사건 B가 일어나는 경우에 사건 A가 일어날 확률 $P(A|B) = {P(A\cap B)\over P(B)}$로 정의한다. 사건 B가 발생했을 때 사건 A가 발생할 확률은 사건 B의 영향을 받아 변하게 된다. 2. Application 조건부 확률에서는 교환 법칙이 성립하지 않는다. 다음과 같은 수식을 보자. $$P(A|B) = {P(A\cap B)\over P(B)}$$ $$P(B|A) = {P(B\cap A)\over P(A)}$$ 이와 같이 교환 법칙이 성립하지 않는다. 이 성질을 이용해 사기꾼들은 교묘하게 약을 팔 수가 있다. 이 내용은 뒤에서 다루도록 한다. 또한, 전체확률의 법칙 (전확률 법..

1. Introduction 아래와 같은 이미지를 본 적이 있는가? 마치 사람의 아이콘처럼 생긴 이미지이다. 사람을 설명할 때 이런 아이콘 이미지를 사용하면 편견이나 혐오감을 주지 않아서 꽤 유용하다. 이런 아이콘을 매번 찾아 다니기도 그렇고 미래에 요구되는 다양한 feature를 전부 저 정할 수도 없는 노릇이다. Avataaars generator는 사용자의 취향에 맞춰 위와 같은 사람 아이콘을 생성해주는 웹사이트이다. 2. Approach Avataaars generator 웹사이트에 들어가면 다음과 같은 페이지가 보인다. 여기서 각종 feature들을 조절하여 원하는 아이콘을 만들어 낼 수 있다. 또한 랜덤 생성도 지원하기 때문에 매우 편리하다. 필자는 논문의 그림 작성 중, User를 표현할 때..

1. Introduction 3중 병합 정렬은 전체 리스트를 3단계로 나눠 분할 정복하는 merge sort의 variation이다. 2. Approach 다음 코드는 파이썬에서 구현한 3중 병합 정렬이다. def threeWayMergeRun(arr, a, b): threeWaySplit(arr, a, b+1, arr[:]) def threeWaySplit(arr, low, high, clone): if high - low < 2: return mid1 = low + ((high - low) // 3) mid2 = low + 2 * ((high - low) // 3) + 1 threeWaySplit(clone, low, mid1, arr) threeWaySplit(clone, mid1, mid2, ar..

1. Introduction 병합 정렬은 프로그램 내장 방식으로 유명한 존 폰 노이만에 의해 제안된 정렬 알고리즘이다. 분할 정복법을 기반으로 하여 주어진 리스트를 분할하고 정렬하여 다시 병합한다. 병합 정렬은 최선, 최악, 평균 상황에서 항상 시간복잡도가 $O(nlog\; n)$임을 보장하며 stable한 알고리즘이다. 구현 방식에는 Top-down 방식과 Bottom-up 방식이 있다. 2. Approach 다음 이미지는 병합 정렬의 과정을 보여준다. 출처는 위키피디아. 다음 코드는 Top-down merge sort를 파이썬에서 구현한 것이다. def topDownMergeRun(arr, a, b): clone = arr[a:b+1] topDownMerge(clone) arr[a:b+1] = clo..

1. Introduction 쉘 정렬은 삽입 정렬이 어느정도 정렬된 리스트에서 좋은 효율을 보인다는 점에서 착안한 삽입정렬의 variation이다. gap에 따라, 떨어진 원소들을 먼저 정렬하고 gap을 줄여나가면서 정렬을 완성하는 정렬 알고리즘이다. 2. Approach 다음 이미지는 쉘 정렬의 과정을 보여준다. 출처는 위키피디아. 다음 코드는 파이썬으로 구현한 쉘 정렬이다. def shell(arr, a, b): n = b-a gap = n//3 + 1 while gap > 0: for i in range(a+gap,b+1): temp = arr[i] j = i while j >= gap and arr[j-gap] >temp: arr[j] = arr[j-gap] j -= gap arr[j] = tem..

1. Introduction 삽입 정렬은 원소가 들어갈 자리를 찾고 그 위치에 삽입한 뒤, 그 보다 큰 원소를 뒤로 밀어내는 방식의 정렬 알고리즘이다. 선택 정렬과 같이 $O(n^2)$의 시간 복잡도를 가지고 있다. 2. Approach 다음 이미지는 삽입 정렬의 과정을 보여준다. 출처는 위키피디아. 다음 코드는 파이썬에서 구현한 삽입 정렬이다. def insertion(arr, a, b): for i in range(a+1, b+1): key = arr[i] j = 0 for j in range(i-1, a-2, -1): if arr[j] > key: arr[j+1] = arr[j] else: break arr[j+1] = key 3. Discussion 삽입 정렬은 stable한 정렬에 속하며 in-..