분류 전체보기
이산 확률 분포, discrete probability distribution
이산 확률 분포, discrete probability distribution
2018.05.28결합 확률 분포\\[P(X = x, Y = y) = f(x, y)\\]두 개 이상의 확률변수가 동시에 발생할 때의 확률 분포. 당연히 이산 확률 분포, 연속 확률 분포 모두 결합 확률 분포로 나타낼 수 있다.어느 지역에 내린 비의 양과 오염도콜레스테롤의 양과 비만도 음주운전 건수와 사망자수 기댓값\\(E(X) = \Sigma{xf(x)}\\)흔히 구하는 산술 평균을 생각해 보면, 위 식에 \\(f(x) = 1/n\\)를 대입하면 되는 균등 분포라는 것을 알 수 있다. 이산확률분포값들이 따로따로 떨어져 있음. 즉 이산적이다.이산 확률 분포의 확률 질량 함수\\(f(x)\\)는 이산 값으로 정의되며따라서 누적 분포 함수\\(F(x)\\)는 우측 연속인 불연속 그래프로 나타난다.\\(F(x)\\)가 불연속이기..
Meltdown 정리
Meltdown 정리
2018.05.26Meltdown핵심은 2가지다.L1 Cache Hit 시 시간과 아닐 때의 시간 비교파이프라이닝 정리하면 다음과 같은 과정으로 익스플로잇.L1 Cache 크기 만큼의 dummy 배열로 L1 Cache 초기화배열 잡고 원하는 데이터(Kernel space data)를 index로 배열에 접근하여 해당 index번째를 L1 Cache에 적재. 즉 index=target data.user mode에서 kernel space 접근하면 보호비트 보고 fault를 일으키지만, 파이프라이닝 때문에 fault가 발생하기 전에 이미 L1 Cache에 타겟 데이터가 적재된 상태. fault는 commit 단계에서 발생하기 때문에 이전 명령어가 이미 execute 단계를 지난 상태. 배열에서 데이터 하나씩 조회해보다가, 다..
액티비티 : Activity life cycle, 백스택, singleTop
액티비티 : Activity life cycle, 백스택, singleTop
2018.05.20https://developer.android.com/guide/components/activities/activity-lifecycle?hl=ko https://developer.android.com/guide/components/tasks-and-back-stack?hl=ko
AlertDialog, Snackbar, Toast / String resource
AlertDialog, Snackbar, Toast / String resource
2018.05.20AlertDialog```ktfun finishDialog(activity : AppCompatActivity, title : String?, message : String?) { AlertDialog.Builder(activity).setTitle(title) .setMessage(message) .setCancelable(false) .setPositiveButton("종료", { _, _ -> activity.finish() }).show()}```내부에서 ``kt ContextThemeWrapper``를 사용하기 때문에 ``kt baseContext``를 넘기면 강제 종료된다. Snackbar```ktlistView.setOnItemClickListener { parent, v, position,..
Design Pattern, 디자인 패턴
Design Pattern, 디자인 패턴
2018.05.14이 글은 보호되어 있기 때문에 이것을 보려면 암호가 필요합니다.
선형 시간 안에 중앙값 선택하기
선형 시간 안에 중앙값 선택하기
2018.05.10최악의 경우에도 선형 시간에 중간값을 선택할 수 있는 알고리즘은 다음과 같다. * 아래는 median을 찾는 예이지만, k번째 작은 값 찾는 문제에 적용 가능하다. ``c Element select(SetOfElements S, int k)`` 중앙값만 찾는 거라면 k 파라미터가 필요 없지만, 일반적인 선택 문제로 확장하면 k 파라미터가 필요함. k는 몇번째로 큰 값을 찾을건지. k번째로 작은 값을 찾는다. `` k=n/2`` 를 넘기면 중간값을 찾겠다는 것. 알고리즘 (k번째 작은 값 찾기를 이용해 median 찾는 예제) 1. 입력 배열이 n개라면 원소 5개짜리 \\(\lceil n/5 \rceil\\) 그룹으로 나눈다. 마지막 집합은 \\(n \mod 5\\)개 원소를 가질 수 있다. 2. 각 그룹..
max, min 동시에 찾기 / 두 번째로 큰 값 찾기
max, min 동시에 찾기 / 두 번째로 큰 값 찾기
2018.05.06min, max 모두 찾을 때 조금 더 효율적인 방법 배열에서 최댓값과 최솟값을 모두 찾는 단순하고 일반적인 방법은 최대키, 최소키를 각각 찾는 방법이다. 이런 방식은 최대키를 찾는데 \\(n-1\\)번 비교, 최소키를 찾는 문제도 이와 같으므로 총 \\(2n-2\\)번 비교하게 된다. 다음과 같은 방법을 사용하면 최댓값과 최솟값을 모두 찾는데 \\(3\lfloor{n/2}\rfloor\\)번만 비교할 수 있다. 입력 원소의 각 쌍에 대해 먼저 둘을 비교한 다음, 큰 쪽을 `` max``와 비교하고 작은 쪽을 `` min``과 비교한다. 이렇게 되면 ``c (max, x1), (max, x2), (min, x1), (min, x2)`` 4번 비교해야 하는 것을 ``c (x1 , x2), (max, x1)..
5개의 원소를 7번 비교로 정렬하기 / 6번 비교로 중간값 찾기 (+ 상대자 논증)
5개의 원소를 7번 비교로 정렬하기 / 6번 비교로 중간값 찾기 (+ 상대자 논증)
2018.05.035개의 원소를 7번 비교로 정렬하기 정렬의 lower bound는 \\(\lceil\lg{n!}\rceil\\)이므로, 5개의 원소를 정렬하려면 최악의 경우 최소 7번은 비교해야 한다. (quick, merge, heap 모두 최악의 경우 8번 비교하게 된다.) 최악의 경우에도 7번만 비교하는 알고리즘의 핵심은 이미 정렬된 부분에 대해서 binary search를 적용한다는 점이다. 이런 류의 정렬 알고리즘의 문제점은 삽입할 위치보다 뒤쪽에 있는 원소들을 모두 한칸씩 밀어내야 한다는 오버헤드가 크다는 점을 고려해야 한다. \\(a, b, c, d, e\\) \\(a > b\qquad\cdots 1\\) \\(c > d\qquad\cdots 1\\) \\(a > c\qquad\cdots 1\\) → {a,..
MIPS celsius to fahrenheit
MIPS celsius to fahrenheit
2018.05.02```py# Celsius to fahrenheit .datamsg:.asciiz "Enter celsius : "const9:.float 9.0const5: .float 5.0const32: .float 32.0zeroF: .float 0.0 .text.globl mainmain: # Expand stack and save $raaddi $sp, $sp, -4sw $ra, ($sp)li $v0, 4# print_str syscall numberla $a0, msg# arg0 : msgsyscallli $v0, 6# read_float syscall numbersyscall# $f0 - user input float numberjal c2fli $v0, 2# print_float syscall numbe..
조건부 확률과 베이즈 정리 (Bayes' theorem)
조건부 확률과 베이즈 정리 (Bayes' theorem)
2018.04.21조건부 확률사건 B가 일어났다는 전제 하에 사건 A가 일어날 확률.사건 B가 이미 일어났으니 \\(P(B)\\)를 전체로 보고 \\(P(A \cap B)\\)를 구하면 된다.\\[P(A|B) = \frac{P(A \cap B)}{P(B)}\\]* 이를 이용해 A, B가 독립이면 \\(P(A \cap B) = P(A)P(B)\\)를 유도할 수 있다. ** \\(A^c\\)에도 성립한다. 베이즈 정리사전확률 \\(P(A)\\)를 알 때, 사후확률 \\(P(A|B)\\)를 구하는데 쓴다.\\(P(A)\\) 희귀병 감염률이 0.001\\(P(B|A)\\) 질병에 걸린 사람이 검사에서 양성 반응을 보일 확률은 0.995\\(P(B|A^c)\\) 질병에 걸리지 않은 사람이 검사에서 양성 반응을 보일 확률은 0.01..
점근적 표기 / 평균 수행 시간 분석
점근적 표기 / 평균 수행 시간 분석
2018.04.20\\(f(n) = \Theta(g(n)) \approx a = b\\)\\(f(n) = O(g(n)) \approx a \le b\\)\\(f(n) = \ o(g(n)) \approx a b\\) \\(W(n) = \max\{\ t(I)\ |\ I \in D_n \}\\) 평균 수행 시간 분석\\[A(n) = \sum_{I \in D_n} Pr(I)t(I) \\]이는 \\(E(x)\\)를 구하는 공식과 같은데, 생각해보면 입력\\(I\\)가 주어졌을 때의 수행 횟수\\(t(I)\\)들의 평균(기대값)을 구한 것이 평균 복잡도이기 때문이다. 평균 수행 횟수는 \\(Pr(I)\\)가 어떻게 정의되느냐에 따라 달라지는데, 각각의 \\(t(I)\\)가 발생할 확률이 모두 동일하다면 간단히 구할 수 있어 별 문제..
피보나치 수
피보나치 수
2018.04.20\\(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...\\) 피보나치 수는 다음 점화식으로 정의된다. \\(F_0 = 0\\)\\(F_1 = 1\\)\\(F_i = F_{i-1} + F_{i-2}\qquad(i \ge 2)\\) 보통 피보나치 수를 구할 때 앞에서부터 두항 씩 더해 구해나갈텐데, 다음 성질을 이용해서 구하는 방법도 있다. 피보나치 수는 황금률 \\(\phi\\)와 그 켤레수 \\(\hat{\phi}\\)와 관련이 있다.\\(\phi\\)와 \\(\hat{\phi}\\)는 다음 방정식의 두 근이다.\\(x^2 = x + 1\\)\\(\phi = {1+\sqrt{5} \over 2} \qquad \quad \hat{\phi} = {1-\sqrt{5} \over 2}\\..