비둘기집 원리 비둘기집 원리 (pigeonhole principle) $n$개의 비둘기 집에 $(n + 1)$마리 이상의 비둘기가 들어갔다면, 두 마리 이상의 비둘기가 들어간 집이 적어도 하나 있음

조건부 확률 조건부 확률 (conditional probability) 어떤 사건이 일어나는 경우에 다른 사건이 일어날 확률. 사건 $A$가 일어나는 경우에 사건 $B$가 일어날 확률을 $P(B|A)$로 표기함 $$ P(B|A) = {P(A \cap B) \over P(A)} $$ 베이즈 정리 베이즈 정리 (Bayes’ theorem) 표본 공간이 $n$에서 서로 다른 배반적인 사건 $B_1, B_2, \cdots, B_n$ 중 하나는 반드시 일어난다고 할 때 두 원인 중 하나일 확률을 구하는 정리. $$ P(B|A) = {P(A|B)P(B) \over P(A)} $$ $$ P(B_k|A) = {P(A|B_k)P(B_k) \over P(A|B_1)P(B_1) + P(A|B_2)P(B_2) + \cdots..

이산적 확률 이산적 확률 (discrete mathematics) 확률 변수 $X$가 이산적인 값을 취했을 때의 확률 확률 분포 확률 분포 (probability distribution) 확률 변수 $X$가 특정한 값 $x_1$을 가질 확률 $p_i$와의 대응 관계를 나타내는 함수. 평균, 분산, 표준편차 평균 (expectation): $E(X) = \sum_{i = 1}^n x_ip_i$ 분산 (variance): $V(X) = E((X-m)^2)$ 표준 편차 (standard deviation): $\sigma(X) = \sqrt{V(X)}$

경우의 수 합의 법칙 합의 법칙 (rule of sum) 두 사건 $A$, $B$가 일어날 경우의 수 $$ n(A \cup B) = n(A) + n(B) = m + n $$ 곱의 법칙 곱의 법칙 (rule of product) 두 사건 $A$, $B$가 동시에 일어날 경우의 수 $$ n(A \cap B) = n(A) \times n(B) = m \cdot n $$ 순열 순열 (permutation) 서로 다른 원소들을 순서를 고려하여 일렬로 배열하는 것. 서로 다른 $n$개의 원소 중 $r$개를 택하는 순열의 수: $_nP_r$ $$ _nP_r = n \times (n - 1) \times (n - 2) \times \cdots \times (n - r + 1) $$ 조합 조합 (combination) ..

동형 그래프 동형 그래프 (Isomorphic graph) 그래프 $G_1 = (V_1, E_1)$과 $G_2 = (V_2, E_2)$가 주어졌을 때 전단사 함수 $f: V_1 → V_2$가 존재하여 $\{u, v\} \in E_1 \iff \{f(u), f(v)\} \in E_2$이면 $f$를 동형(isomorphism)이라 하고 $G_1$과 $G_2$를 동형 그래프라 함 완전 그래프 완전 그래프 (complete graph) 그래프 $G = (V, E)$의 모든 정점들의 쌍 사이에 연결선이 존재하면 $G$를 완전 그래프라 함. $n$개의 정점으로 구성된 완전 그래프는 $K_n$으로 표기함 정규 그래프 정규 그래프 (regular graph) 그래프 $G = (V, E)$의 모든 정점의 차수가 $k$이..

해밀턴 경로 해밀턴 경로 (Hamiltonian path) 그래프에서 모든 정점을 오직 한 번씩 지나는 경로. 시작점으로 돌아오지 않음 해밀턴 순회 해밀턴 순회 (Hamiltonian circuit) 그래프에서 모든 정점들을 오직 한 번씩만 지나는 순회 외판원 문제 외판원 문제 (traveling salesperson problem) 방문해야 할 도시들과 도시들 사이의 거리가 주어짐. 외판원이 특정 도시에서 출발해 각 도시를 한 번씩 방문하며 모든 도시들을 거쳐 처음 출발한 도시로 되돌아올 때 최소 비용이 드는 경로를 찾는 문제 외판원 문제는 해밀턴 순회를 응용한 문제입니다. 따라서 해밀턴 순회와 같이 외판원 문제는 다항 시간 안에 푸는 알고리즘이 발견되지 않아 NP-난해 문제에 속합니다. 이 문제는 정..

오일러 경로 오일러 경로 (Euler path) 그래프에서 각 연결선을 단 한 번씩만 통과하는 경로 오일러 경로에서는 시작 정점과 끝 정점을 제외하고 모든 정점의 차수가 짝수입니다. 즉, 시작 정점과 끝 정점의 차수는 홀수여야만 합니다. 오일러 순회 오일러 순회 (Euler circuit) 그래프에서 정점은 여러 번 지날 수 있지만, 각 연결선을 단 한 번씩만 통과하는 순회를 말함 오일러 순회는 모든 정점의 차수가 짝수입니다. 그래서 어떤 그래프가 오일러 순회를 만족하는지 알기 위해서 모든 정점의 차수가 짝수인지 확인하면 됩니다.