확률 (Probability)

정의

확률 (Probability) 은 사건이 발생할 가능성을 수치화한 값. 표본 공간 Ω 에 대해 P(A) = |A| / |Ω| (동일 확률), 또는 더 일반적으로는 σ-algebra 위의 측도론 정의. 알고리즘 문제에서는 주로 조합론적 확률 + 조건부 확률 + 기댓값 선형성 으로 수식화.

문제 상황과 동기

“확률적 사건” 을 모델링해야 하는 모든 문제 (카드 뽑기, 주사위, 랜덤 이동, 기댓값 DP).

• naive: 모든 경우를 직접 시뮬레이션. O(2^N) 또는 무한 상태.
• 확률 공식: 조건부 확률, 독립성, 전확률 공식, 베이즈를 이용해 수식 단순화. O(N) ~ O(N²).

핵심 통찰: 덧셈 원리, 곱셈 원리, 여사건, 조건부 확률 으로 경우의 수를 기하급수적으로 줄일 수 있다. 기댓값 선형성 으로 복잡한 랜덤 변수도 분해.

PS 에서는 모듈러 역원 (mod 10^9+7) 로 분수 확률을 정수화하는 패턴이 자주 등장.

시각화

핵심 아이디어

기본 공리

1. 비음성: P(A) ≥ 0
2. 정규화: P(Ω) = 1
3. 덧셈: A ∩ B = ∅ ⇒ P(A ∪ B) = P(A) + P(B)

조건부 확률

P(A | B) = P(A ∩ B) / P(B)

사건 B 가 일어났다는 전제 하에 A 의 확률. 표본 공간을 B 로 축소.

독립성

P(A ∩ B) = P(A) · P(B) ⟺ A, B independent

전확률 공식 (Law of Total Probability)

P(A) = Σᵢ P(A | Bᵢ) · P(Bᵢ)

B₁, B₂, … 가 partition (서로 배타, 합집합 Ω).

베이즈 정리

P(A | B) = P(B | A) · P(A) / P(B)

원인-결과 역전. 조건부 확률 계산에 핵심.

기댓값 선형성

E[X + Y] = E[X] + E[Y]

독립이 아니어도 성립. 복잡한 확률 변수를 분해하는 강력한 도구.

알고리즘

동일 확률 (uniform):
  P(A) = |A| / |Ω|

조건부 확률:
  P(A | B) = P(A ∩ B) / P(B)

베이즈:
  P(A | B) = P(B | A) · P(A) / P(B)

기댓값:
  E[X] = Σ x · P(X = x)
  E[aX + bY] = a·E[X] + b·E[Y]

구현

// 모듈러 확률: 분수 p/q → p·q⁻¹ (mod M)
// fermat little: q⁻¹ = q^(M-2) mod M (M prime)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
​
long long power(long long a, long long n) {
  long long r = 1;
  for (; n; n >>= 1, a = a * a % MOD)
      if (n & 1) r = r * a % MOD;
  return r;
}
long long inv(long long x) { return power(x, MOD - 2); }
​
int main() {
  // 문제: 동전 n 번 던져 앞면 k 번 나올 확률 (C(n, k) / 2^n) mod M
  int n, k; cin >> n >> k;
  
  // C(n, k) 계산
  long long num = 1, den = 1;
  for (int i = 0; i < k; i++) {
      num = num * (n - i) % MOD;
      den = den * (i + 1) % MOD;
  }
  long long nCk = num * inv(den) % MOD;
  
  // 2^n
  long long pow2n = power(2, n);
  
  // 확률 = C(n, k) / 2^n
  long long prob = nCk * inv(pow2n) % MOD;
  cout << prob << "\n";
}

# Python 은 Fraction 으로 정확한 분수 계산
from fractions import Fraction
from math import comb
​
def coin_probability(n, k):
  """동전 n 번 중 k 번 앞면 확률"""
  return Fraction(comb(n, k), 2 ** n)
​
def conditional_prob(p_ab, p_b):
  """P(A | B) = P(A ∩ B) / P(B)"""
  return p_ab / p_b if p_b > 0 else 0
​
def bayes(p_b_given_a, p_a, p_b):
  """베이즈: P(A | B) = P(B | A) · P(A) / P(B)"""
  return p_b_given_a * p_a / p_b if p_b > 0 else 0
​
n, k = map(int, input().split())
prob = coin_probability(n, k)
print(f"{prob.numerator}/{prob.denominator}")  # 분수 출력
print(f"{float(prob):.6f}")  # 실수 출력

// 모듈러 역원으로 분수 확률 계산
import java.util.*;
import java.io.*;
​
public class Main {
  static final long MOD = 1_000_000_007;
  
  static long power(long a, long n) {
      long r = 1;
      for (; n > 0; n >>= 1, a = a * a % MOD)
          if ((n & 1) == 1) r = r * a % MOD;
      return r;
  }
  static long inv(long x) { return power(x, MOD - 2); }
  
  static long comb(int n, int k) {
      long num = 1, den = 1;
      for (int i = 0; i < k; i++) {
          num = num * (n - i) % MOD;
          den = den * (i + 1) % MOD;
      }
      return num * inv(den) % MOD;
  }
  
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken());
      
      // C(n, k) / 2^n
      long nCk = comb(n, k);
      long pow2n = power(2, n);
      long prob = nCk * inv(pow2n) % MOD;
      System.out.println(prob);
  }
}

5 2

500000007
0.312500

10 5

20116005
0.246094

복잡도

기댓값 DP 는 문제별로 O(N) ~ O(N²).

조건부 확률과 베이즈 정리

조건부 확률 예시

문제: 두 주사위를 던져 합이 7 일 때, 첫 번째 주사위가 3 일 확률?

• B = “합이 7” → 경우 (1,6), (2,5), (3,4), (4,3), (5,2), (6,1) 총 6 개
• A = “첫 번째 3” ∩ B = (3, 4) 총 1 개
• P(A | B) = 1/6

베이즈 정리 예시

문제: 질병 발병률 0.1%, 검사 정확도 99%. 양성이 나왔을 때 실제 병일 확률?

P(병 | 양성) = P(양성 | 병) · P(병) / P(양성)
P(양성) = P(양성 | 병)·P(병) + P(양성 | 건강)·P(건강)
        = 0.99 · 0.001 + 0.01 · 0.999 ≈ 0.01098
P(병 | 양성) ≈ 0.99 · 0.001 / 0.01098 ≈ 0.090 (약 9%)

직관과 다르게 낮은 prior 때문에 양성이어도 실제 병일 확률은 9% 정도.

기댓값 선형성 활용

문제: 길이 n 순열에서 i < j 인데 a[i] > a[j] 인 쌍 (inversion) 의 기댓값?

• 각 쌍 (i, j) 가 inversion 일 확률 = 1/2
• 전체 쌍 개수 = C(n, 2) = n(n-1)/2
• E[inversion] = Σ P(i, j inversion) = n(n-1)/4

독립이 아니어도 선형성으로 기댓값 분해 가능.

변형 / 활용

함정

1. 조건부 확률 착각

P(A | B) ≠ P(B | A). 베이즈 정리 없이 직접 뒤집으면 틀림.

2. 독립성 가정

사건이 실제로는 독립이 아닌 경우 P(A ∩ B) = P(A) · P(B) 쓰면 오답.

3. mod 역원 존재

MOD 가 소수일 때만 페르마 소정리 적용. 합성수면 확장 유클리드.

4. 0 나누기

P(A | B) 계산시 P(B) = 0 이면 정의 안 됨. 분기 필요.

5. 실수 정밀도

확률을 double 로 계산할 때 누적 오차. 분수 또는 모듈러 정수로 정확 계산.

BOJ 연습 문제

참고

• 조합론
• 기댓값
• 마르코프 체인
• 모듈러 연산