Clean Code hochulshin.com

Algorithm - 독립 시행 확률

2015-08-16

예제를 통해 독립 시행 확률을 계산하는 방법을 알아보자.

문제

가구를 만드는 공장이 있다. 숙련된 가구 장인은 혼자서 하나의 가구를 5분만에 만들어 낸다. 그러나 가구를 만들어도 결함이 있을 수 있다. 결함이 없는 가구를 완제품이라고 한다. 사장은 두 명의 가구 장인에게 90분동안 가구를 만드는 시함을 시켰다. 그런데 사장은 두 가구 장인이 만들어 내는 완제품의 수가 최소한 한 명이라도 소 수 일 확률이 궁금해 졌다.

가구 장인 A, B가 있을 때 평소 각 장인의 5분안에 완제품을 만들 확률이 주어진다. pA는 A장인이 5분안에 완제품을 만들 확률이며, pB는 B장인이 5분안에 완제품을 만들 확률이다. 각 가구 장인이 만든 완제품의 수가 최소 한 명이라도 소수일 확률을 구하는 프로그램을 작성하라. 예를 들어 pA가 100%, pB가 100%일 경우 최종적으로 A는 18개, B도 18개를 만들어 내고 18은 소수가 아니기 때문에 소수일 확률은 0.00이다.

제약 사항

0<= pA, pB <= 100

입력

맨 위줄에 테스트 케이스 수가 주어지고, 그 뒤 한 줄씩 테스트 케이스의 입력 pA와 pB가 주어진다.

2
0 0
80 90

출력

완제품이 최소 한명이라도 소수일 확률을 각 테스트 케이스 별로 출력한다. 이때 확률의 출력은 소수점 6자리를 넘어가면 소수점 7번 자리에서 반올림한다.

#1 0.000000
#2 0.503683

아이디어

18번의 시도를 통해 2개, 3개, 5개… 17개 등 소수 개의 완성품을 확률을 각기 계산하여 합산하면 된다. 그렇게 하기 위해서는 n번의 서로 독립적인 사건 중 r번이 발생할 확률이 얼마인지 계산하는 독립 시행 확률을 계산할 수 있어야 한다. 그리고, A와 B 장인의 확률의 합쳐서 계산해야 하므로 확률의 덧셈정리에 대한 이해도 필요하다.

독립 시행 확률

독립 시행이란 동전이나 주사위를 여러 번 던질 때와 같이 어떤 시행을 계속해서 되풀이 할 때, 매번 일어나는 사건이 서로 독립적인 경우 즉, 각 시행의 결과가 다른 시행의 결과에 영향을 미치지 않는 시행을 말한다. 독립 시행의 확률은 어떤 사건 A가 일어날 확률이 p이고, 그 여사건이 일어날 확률이 q(q=1-p)일때, n번의 독립 시행에서 사건 A가 r번 일어날 확률은 다음과 같다.

P(r) = nCr * p의 r제곱 승 * q의 n-r 제곱 승 (r=0, 1, 2, 3, …, n)

조합

서로 다른 n개에서 순서를 생각하지 않고 r개(0<=r<=n)를 택하는 것을 조합이라 하며 그 조합의 수는 다음과 같이 계산한다.

nCr = n factorial / (r factorial * n-r factorial)

참고로 순서를 감안한 경우의 수인 순열은 다음과 같다. 서로 다른 n개 중 r개를 택해 순서대로 나열하는 방법의 수

nPr = n factorial / n-r factorial

확률의 덧셈 정리

두 사건 A, B에 대해 사건 A 또는 B가 일어날 확률은 다음과 같다.

P(AUB) = P(A) + P(B) - P(A와 B의 교집합)

즉, A의 확률과 B의 확률을 더하고, A와 B가 동시에 일어날 확률을 빼면된다. A와 B가 서로 독립적인 것이라면 A와 B가 동시에 발생할 확률은 두 확률을 곱한 확률과 같다.

P(A와 B의 교집합) = P(A)*P(B)

C 구현

#include <stdio.h>

#define SIZE 19 //총 19 케이스 저장(0:18번 중 0개 완성품, 1:18번중 1개 완성품, ... 18:18번중 18개 완성품)

/* Composition을 구하기 위한 factorial 값 저장*/
long long Factorial[SIZE];
long long factorial(int n){
    if(n==1){
        Factorial[0] = 0;
        Factorial[1] = 1;
        return 1;
    }
    long long res = n*factorial(n-1);
    Factorial[n]=res;
    return res;
}
/* n개 중 r개를 선택하는 경우의 수 계산: nCr
   nCr = nfactorial/(rfactorial * (n-r)fractorial) */
int composition(int n, int r){
    if(r == 0 || r==n)
        return 1;
    long long res = Factorial[n]/Factorial[r];
    res /= Factorial[n-r];
    return res;
}

/* 18번 시도하여 소수개의 완성품을 얻을 확률을 그 갯수별로 각각 계산. - 독립 시행 수행 확률 계산 */
double cal(int i_p){
    if(i_p == 0){
        return 0;
    }
    int prime_numbers[7] = {2, 3, 5, 7, 11, 13, 17}; //19의 소수들
    double t_p = i_p;
    double p = t_p/100;//정수 확률을 소수 확률로 전환

    //독립 시행 확률 계산을 위해 제곱승을 각기 계산
    double P[19];   //독립 시행 확률 계산을 위한 확률 p의 r제곱승을 저장하기 위한 배열
    double Q[19];   //독립 시행 확률 계산을 위한 확률 p의 여확률(1-p)의 r제곱승을 저장하기 위한 배열
    P[1] = p;
    Q[1] = 1-p;
    for(int i = 2; i<18; i++){
        P[i] = P[i-1]*p;
        Q[i] = Q[i-1]*(1-p);
    }
    double res = 0;
    //소수 개를 완성품으로 만들 확률
    for(int i = 0; i<7; i++){
        //독립 시행 확률 계산
        //발생할 확률 p를 가진 독립적인 사건을 n번 수행했을 때 r번 그 사건이 발생할 확률 = nCr * p의 r제곱승 * p의 여확률의 n-r 제곱승
        //독립적인 사건이란 한번의 수행 결과가 다음 수행에 영향을 주지 않느 사건: 예- 동전 던져서 앞면이 나올 확률
        res += composition(18, prime_numbers[i])*P[prime_numbers[i]]*Q[18-prime_numbers[i]];
    }
    return res;
}

int main(){
    int testcase;
    int T;
    scanf("%d", &T);
    factorial(18);
    for(testcase = 1; testcase<=T; ++testcase){
        int p_a, p_b;
        scanf("%d %d", &p_a, &p_b);
        double res_a = cal(p_a);
        double res_b = cal(p_b);
        double res = res_a + res_b - res_a*res_b; //동시에 소수가 나올 확률을 제외해야 함
        printf("#%d ", testcase);
        printf("%.6f ", res);
    }
    return 0;
}

Comments