확률(Probability)이란 주어진 데이터 집합에서 원하는 결과가 나올 가능성을 의미합니다. 확률의 값은 항상 0과 1 사이에 존재하며, 0은 불가능함을, 1은 반드시 일어남을 나타냅니다.
확률이란 무엇인가?
수학에서 확률은 사건이 일어날 불확실성을 정량적으로 계산할 수 있게 해주는 도구입니다. 다시 말해 확률은 특정 사건이 발생할 가능성을 0과 1 사이의 숫자로 표현하는 학문이라고 할 수 있습니다.
예를 들어, 편향되지 않은 동전을 던졌을 때 앞면이 나올 확률은 0.5이며, 주사위를 굴렸을 때 3이 나올 확률은 1/6(약 0.1667)입니다.
문제 정의
이번 글에서 다룰 문제는 N번의 동전 던지기에서 적어도 k개의 앞면이 나올 확률을 구하는 것입니다.
예를 들어 동전이 3개(n = 3)이고 k = 2라고 가정해 보겠습니다. 동전을 던지는 경우의 수는 2³ = 8가지로 다음과 같습니다.
HHH, HTH, HHT, HTT, THH, THT, TTT, TTH
이 중 적어도 2개 이상의 앞면(H)을 포함하는 경우는 다음 4가지입니다.
HHH, HTH, HHT, THH
따라서 확률은 4/8, 즉 0.5가 됩니다.
입력 및 출력 예시
입력: k = 1, n = 3
출력: 0.875
입력: k = 3, n = 6
출력: 0.65625
문제 해결 접근 방법
- n과 k를 입력값으로 받습니다.
- 팩토리얼 값을 미리 배열에 저장해 두고, 필요할 때마다 호출하여 사용합니다.
- 조합 공식을 이용해 각 경우의 수를 계산합니다.
- 계산된 결과를 반환합니다.
핵심 아이디어는 조합(combination) 공식입니다. n번의 던지기 중 정확히 i개의 앞면이 나오는 경우의 수는 C(n, i) = n! / (i! × (n-i)!)이며, i를 k부터 n까지 모두 더한 뒤 전체 경우의 수인 2ⁿ으로 나누면 원하는 확률을 얻을 수 있습니다.
알고리즘
Step 1 → 최소 k개의 앞면이 나올 확률을 계산하는 함수 선언
double probability(int k, int n)
double check = 0 으로 초기화
i = k부터 i <= n까지 반복
check += temp[n] / (temp[i] * temp[n - i])
check = check / (1LL << n)
check 반환
Step 2 → 팩토리얼 값을 미리 계산하는 함수 선언
void precompute()
temp[0] = temp[1] = 1 설정
i = 2부터 i < 20까지 반복
temp[i] = temp[i - 1] * i
Step 3 → main 함수
precompute() 호출
probability(1, 3) 호출
종료
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
#define size 21
double temp[size];
// n번의 동전 던지기에서 최소 k개의 앞면이 나올 확률 계산
double probability(int k, int n) {
double check = 0;
for (int i = k; i <= n; ++i)
check += temp[n] / (temp[i] * temp[n - i]);
check = check / (1LL << n);
return check;
}
// 팩토리얼 값 미리 계산
void precompute() {
temp[0] = temp[1] = 1;
for (int i = 2; i < 20; ++i)
temp[i] = temp[i - 1] * i;
}
int main() {
precompute();
// 3개의 동전에서 1개 이상 앞면이 나올 확률
cout<<"probability is : "<<probability(1, 3) < " ";
// 6개의 동전에서 3개 이상 앞면이 나올 확률
cout<<"probability is : "<<probability(3, 6) <<" ";
return 0;
}
실행 결과
probability is : 0.875
probability is : 0.65625
정리
이 알고리즘은 팩토리얼 값을 미리 계산(precompute)해 두기 때문에 각 확률 계산을 O(k) 시간 안에 빠르게 처리할 수 있습니다. 단, 팩토리얼 오버플로우를 방지하기 위해 n의 크기가 제한적일 때(본 예제에서는 20 미만) 사용하는 것이 적합하며, 더 큰 n에 대해서는 로그 기반 계산이나 부동소수점 방식의 조합 계산을 활용하는 것이 좋습니다.