Elevation

표본분포(samplign distribution)이란 통계량의 확률분포를 의미한다. 표본분포를 이용해 통계량의 정확성을 측정할 수 있으며, 통계량의 표본분포에 따라 모집단 예측에 있어 통계량을 어떻게 처리할지가 달라지기 때문에 중요한 개념이다.표본분포는 모집단의 분포와, 표본의 추출 방식(어떻게 뽑을지)에 의해 결정된다. 모집단의 분포는 이미 결정되어 있으므로 결국 통계량을 어떻게 뽑는지에 따라 표본분포가 달라지게 된다.​표본 추출의 방식에 대하여, 단순랜덤추출(SRS)을 사용할 것이나 복원추출할 것인지, 비복원추출할 것인지에 대한 문제가 있다. 복원추출은 계산이 간결하지만 중복 표본이 발생한다는 문제가 있고, 비복원추출은 중복 문제가 없으나 계산이 복잡해진다. 가령 $N$개 중 $M$개가 당첨인 모집단..

요즘 통계학을 배우고 있어 핵심 위주로 가볍게 정리해 본다. 통계학이란?기본적으로 모집단(population)에서 일부에 대한 자료, 즉 표본(sample)을 수집하고 표본을 바탕으로 모집단을 예측하는 학문이다. 전체를 예측하는 데에는 전체를 측정하면 가장 좋겠지만 여러 제약으로 불가능하니 일부로 전체를 추측하는 것이다. 그래서 다음과 같은 전제가 깔려 있다.1) 최선의 예측을 하나, 정확히 맞추는 것을 기대하지 않는다.2) 수리 논리 등을 활용해 추론에 대한 합리성을 부여한다. 즉 왜 이렇게 추론했는지 뒷받침하여 설명한다.3) 오차가 당연히 발생하나 오차를 통제할 수 있기를 기대한다. 측도먼저 주어진 자료의 특성부터 잘 분석할 수 있어야 한다. 자료의 특징을 알기 위한 여러 가지 측도가 있다.제일 중..

그래프 이론의 유명한 문제인 최단 경로 문제를 해결하는 알고리즘에 대해 알아보자. 알고리즘에 따라 사용 가능한 조건과 얻을 수 있는 결과가 다르기 때문에 상황에 맞는 알고리즘을 잘 골라서 사용하는 것이 중요하다. 다익스트라다익스트라(Dijkstra) 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 꽤 빠른 시간 안에 동작하나 가중치가 양수여야 한다는 제한조건이 있다. 이는 다익스트라가 (전체 최단 경로)=(부분 최단 경로들의 합)이라는 그리디한 접근으로 동작하기 때문이다.* 참고: 다익스트라의 초기 아이디어는 그리디이나, 효율성을 위해 힙을 사용하게 되면서 힙에 방문한 정점을 중복해서 넣는 방식으로 구현하면 일종의 백트래킹처럼 동작한다. 이 경우 음수 가중치의 간선도 ..

서로소 집합서로소 집합(Disjoint set)은 Union-find 알고리즘으로도 많이 불리는데, 서로 겹치는 원소가 없으면서 전체 원소를 포괄하는 집합들의 처리와 관련된 알고리즘이다. 즉 서로소 집합에서 모든 원소는 각각 정확히 1개의 집합에 속하게 된다. 서로소 집합이 지원하는 연산은 2가지이다.​$find(x)$: 원소 x가 속한 집합을 출력한다.$union(a, b)$: 원소 a가 속한 집합과, b가 속한 집합을 합친다.​두 연산을 구현하기에 최적화된 자료구조는 트리이다. 트리를 이용하면 루트 노드를 집합명으로 사용하여 다음과 같이 이해할 수 있다.​$find(x)$: x가 속한 트리의 루트 노드를 출력한다.$union(a, b)$: a와 b가 속한 트리의 루트 노드를 각각 구하여, 둘 중 하나..

DAG방향 비순환 그래프(Directed Acyclic Graph, DAG)란 방향 그래프 중 cycle이 없는 그래프를 뜻한다. cycle이 없기 때문에 linearlization이 가능하다. 이렇게 우선순위에 맞게, 즉 화살표가 오른쪽으로만 향하게끔 정점들을 정렬하는 것을 위상 정렬(Topological sort)이라 한다. 위상 정렬의 해답은 여러 개일 수 있다. DAG는 전체 대상 중 두 대상 간의 관계가 여러 차례 제시된 경우 성립할 수 있다. ex) 두 학생의 키를 비교하거나, 두 과목 간의 위계가 제시된 경우 이때 위상 정렬 알고리즘을 통해 제시된 관계들을 만족시키는 전체 대상들의 순서를 구할 수 있다. DFS를 이용한 위상 정렬위상 정렬의 구현 방법으로는 대표적으로 2가지가 제시되어 있..

그래프의 구현그래프는 인접 리스트나 인접 행렬로 구현한다.인접 리스트: 한 정점과 연결되어 있는 다른 정점들을 연결리스트로 표현인접 행렬: $N \times N$ 행렬을 이용해 정점끼리 연결되어 있으면 1, 없으면 0으로 표현간선 수가 적은(sqarse한) 경우에는 인접리스트가 더 유리하다.​아래는 노드 $N$개와 간선 $M$개가 주어질 때 인접 리스트로 무방향 그래프를 표현하는 코드이다.N, M = map(int, input().split())adj = defaultdict(list)for _ in range(M): u, v = map(int, input().split()) adj[u].append(v) adj[v].append(u) 인접 행렬은 2차원 배열을 이용해서 다음과 같이 표현..