Elevation

전편에서는 범주형 자료에 대해, 모비율을 추정 혹은 검정의 대상으로 삼아 2개 이하의 집단에서 분석하는 방법을 살펴보았다. 그러나, 3개 이상의 범주형 자료에 대해 분석해야 하는 상황도 있을 것이다. 이럴 경우, 귀무가설은 모든 모수가 같다($p_1 = p_2 = p_3$)는 가설으로, 대립가설은 그렇지 않다(즉, 최소 1개의 모수는 다르다)는 가설으로 놓고 검정한다. 전체적으로 검정한 후에, 귀무가설을 기각하면 둘씩 묶어 세부 검정하는 방식으로 어떤 모수가 다른지를 찾는다. '어차피 세부 검정을 진행해야 한다면, 전체 검정할 필요 없이 처음부터 둘씩 묶어서 비교하여 결론을 내면 되지 않을까'라고 생각할 수 있는데, 그렇게 진행하면 전체 결론이 맞기 위해서 세부 검정이 모두 맞아야 하기에 $(1-\alp..

표본분포dbinom(x, size, prob)$X \sim B(n, p)$에서 $P(X=x)$. x에는 벡터가 들어갈 수 있다. pbinom(x, size, prob)dbinom의 누적 합이다.pbinom의 역함수로, 백분위를 x로 바꿔주는 qbinom()도 있다. dnorm(x, mean, sd)$X \sim N(\mu, \sigma^2)$에서 $P(X=x)$를 계산하고 사용방법은 비슷하다.for(i in 5:0){ print(dbinom(i, size = 10, prob = 0.7))}pbinom(5, size = 10, prob = 0.7)sum(dbinom(0:5, size = 10, prob = 0.7))dnorm(seq(1,5), mean=0, sd=1) 데이터 불러오기setwd(dir),..

지금까지는 연속형 자료들의 핵심 모수인 평균 및 분산에 관해 통계적 추론을 진행하였다. 범주형 자료로 대표되는 이산형 자료를 만났을 경우에는 어떻게 통계적 추론을 할 수 있을지 정리해 보자. 모비율의 추정 및 검정이산형 자료의 경우 관심 모수는 무한모집단에서 특정 카테고리의 비율인 모비율(population proportion, $p$)이다. 모비율을 추정하기 위해서 표본비율(sample proportion, $\hat{p}$)을 사용하며, 이는 당연히 $n$개의 랜덤 표본 중 특정 속성의 개체 수 $X$의 비율인 $\frac{X}{n}$으로 정의된다. 표본비율의 분포를 살펴보기 위해 베르누이 분포와 이항분포의 개념을 다시 떠올려 보자. 표본을 추출하는 과정은 $Ber.(p)$에서 i.i.d.하게 $..

모분산에 대한 추정 및 검정모평균에 대한 가설 검정을 수행했던 것과 비슷하게, 모집단의 변동성에 관심이 있다면 모분산에 대한 가설 검정을 진행할 수 있다. 우리의 관심 대상 $\sigma^2$에 대응되는 추정량(혹은 검정통계량)은 표본분산 $S^2$이 되고, 모집단의 정규성 가정 하에 표본분산은 적절한 표준화를 통해 카이제곱 분포로 나타낼 수 있다. $$\frac{(n-1)S^2}{\sigma^2} \sim \chi^2 (n-1)$$ 식을 변형하여 $\sigma^2$에 대한 추정 및 신뢰구간을 구하는 것은 어렵지 않을 것이다. 다만 모평균 $\mu$를 추정할 때는 Z-분포의 대칭성을 생각하면 $z_{1-\alpha/2}=-z_{\alpha/2}$으로 계산하는 것이 가능했지만, 카이제곱분포는 대칭적이지 않..

계속해서 검정을 다룬다. 이번에는 두 모집단에서 추출한 이표본(two-samples)을 비교할 때의 가설 검정에 대해 다뤄볼 것이다. 실험에서 어떠한 두 가지 방법의 결과가 유의미하게 차이가 있는지 확인하기 위하여, 이표본 검정을 사용할 수 있다. 이표본에 의한 모평균 비교가령 두 가지 약의 효능에 차이가 있는지 비교하는 검정을 한다고 생각해 보자. 두 모집단은 서로 독립적이므로, 각각의 모집단에서 추출한 랜덤 표본인 이표본 역시 독립적이라고 볼 수 있다. 한편 우리가 확인하고 싶은 것은 두 집단의 모평균 차 $\mu_1 - \mu_2$의 통계적 유의성이므로, 검정통계량은 $\overline{X}_1-\overline{X}_2$가 된다. 이제 검정통계량이 무슨 표본분포를 따를지 알아보자. 서로 독립적이..

이분 그래프(bipartite graph)란 정점을 두 그룹($A, B$)로 나눴을 때, $A$와 $B$ 간에만 간선이 존재하고 그룹 내부에는 간선이 존재하지 않도록 만들 수 있는 그래프를 의미한다. 어떤 그래프가 이분 그래프인지 판별하는 방법은 간단하다. 탐색을 수행하면서 정점을 빨강/파랑으로 색칠해 주는데, 빨강색 정점에 인접한 정점은 모두 파란색으로 색칠되어야 하며, 파랑색 정점에 인접한 정점은 모두 빨간색으로 색칠되어야 한다. 그렇지 않으면 이분 그래프라고 볼 수 없다. 이분 매칭(bipartite matching)은 이분 그래프에서 최대 매칭을 찾는 알고리즘이다. 매칭(matching)은 정점을 공유하지 않도록 간선을 선택하는 방법이다. 정점의 입장에서는 최대 하나의 다른 정점과 연결되도록 하는..

MCMF최대 유량(플로우)의 심화 버전인 최소 비용 최대 유량 문제(Min-cost Max-flow, MCMF)에 대해 알아보자. 말 그대로 최대 유량을 흘리되, 사용하는 간선의 비용 합이 최소가 되도록 하는 문제이다. 최대 유량과 마찬가지로 이용 가능한(즉, $capacity - flow > 0$) 간선으로 이루어진 경로를 찾고, 흘릴 수 있는 최대 유량 $f$를 구하여, 정방향으로 유량 $f$를 흘리고 역방향으로 $-f$를 흘리는 것은 동일하다. 정방향과 역방향이 모두 정의되는 유량 $flow$와 달리, 용량 $capacity$의 경우 source → sink의 단방향으로만 정의함에 주의하여 구현하는 것 역시 동일하다. 차이점은 최소 비용의 경로를 찾아야 하기 때문에, 경로 탐색에 단순 bfs/dfs..

비트마스킹(bitmasking)은 기본적으로 이진수 표현을 활용해서 자료를 저장하는 기법이다. 컴퓨터는 기본적으로 이진수 단위로 연산하다 보니 비트마스킹을 활용하면 메모리와 시간의 절약이 가능하다. 가령 0과 1로만 이루어진 자료를 표현할 때, [0, 1, 1, 0, ...]처럼 정수의 배열로 표현하는 것보다는, 0110...(2)로 묶어 하나의 정수로 담으면 더 효율적일 것이다. 다만 ps에서 비트마스킹이 필수일 정도로 시간/공간복잡도가 빡빡한 문제는 많지는 않다. 대신 이렇게 비트필드를 이용하면 자료를 하나의 수로 표현할 수 있음을 이용해, 서브 문제의 상태를 비트마스킹하여 dp 배열에 저장하는 방식으로 문제를 푸는 기법이 있다. 이를 비트필드를 이용한 DP라고 한다. 외판원 순회 문제(TSP)TS..

CCW(Counter Clockwise)란 세 점의 진행 방향이 시계 반대 방향인지, 시계 방향인지 판단할 수 있게 해 주는 알고리즘이다.$CCW(A, B, C)$는 세 점을 입력으로 받아 직선 $AB$와 점 $C$의 위치 관계를 판단한다. $C$가 직선 $AB$에 비해 반시계 방향으로 진행한다면 양수를, 시계 방향으로 진행한다면 음수를, 직선 위에 있다면 0을 반환한다. CCW 알고리즘은 벡터의 외적을 활용한다. 두 벡터 $\overrightarrow{AB}$와 $\overrightarrow{AC}$를 외적하면 그 부호는 오른손 법칙에 의해 결정되는 외적의 방향을 의미한다. $\overrightarrow{AB}$에 비해 $\overrightarrow{AC}$가 시계 반대 방향이라면 외적은 2차원 평면을..

4단계를 다 풀었다. 난이도는 실버 상위~골드 하위 수준이고 dp, 그래프 탐색, 백트래킹, 구현 위주의 문제가 많았다. 한문제씩 풀 때는 그렇게 오랜 시간이 걸리지 않았는데, 확실히 정해진 48문제를 다 푸는 것은 마냥 쉽지는 않은 것 같다. 푼 문제 수가 늘어갈수록 남아있는 문제들은 더 까다롭게 다가오는 느낌이었다. 아이디어가 떠오르지 않아서 자력으로 푸는 데 꽤 많은 시도를 한 문제들도 있었다. 아무튼 이번에 새로 배웠거나 헷갈리는 개념(문제)들 위주로 간단히 정리해 본다. LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)LIS 자체는 dp로 $O(N^2)$만에 해결 가능하다. 수열 $A$에 대해 $dp[i]$=($A[i]$까지의 LIS)라고 생각하면,..