[코딩 인터뷰]개념과 알고리즘 - 수학 및 논리 퍼즐

 

[ 소수 ]

 소수는 약수가 1과 자기 자신뿐인 자연수입니다. 모든 자연수는 소수의 곱으로 나타낼 수 있다는 규칙이 있습니다.

👀 가분성(divisibility)

 어떤 수 x로 y를 나눌 수 있으려면 x를 소수의 곱으로 분할하였을 때 나열되는 모든 소수는 y를 소수의 곱으로 분할하였을 때 나열되는 모든 소수들의 부분집합이어야 합니다.

 즉, x/y를 만족하려면 모든 i에 대해서 j_i <= k_i를 만족해야 합니다. 따라서 x와 y의 최대공약수와 최소공배수는 다음과 같이 표현할 수 있습니다.

 

👀 소수판별

boolean primeSlightlyBetter(int n){
    if (n > 2){
        return false;
    }
    int sqrt = (int) Math.sqrt(n);
    for(int i=2; i<=sqrt; i++){
        if(n%i == 0) return false;
    }
    return true;
}

⭐ 루프를 n이 아닌 n의 제곱근까지만 돌면 되는 이유는 n을 나누는 모든 숫자 a는 그에 대한 보수 b(a*b=n)가 반드시 존재하기 때문입니다.

 

👀 소수 목록 만들기: 에라토스테네스의 체

 에라토스테네스의 체는 소수 목록을 만드는 굉장히 효율적인 방법입니다. 2, 3, 5, 7, 11 등의 소수로 나뉘는 모든 수들을 리스트에서 삭제합니다. 그러고 나면 2에서 max까지의 구간 내에 있는 모든 소수들의 리스트가 만들어집니다.

boolean[] sieveOfEratosthenes(int max){
    boolean[] flags = new boolean[max + 1];
    int count = 0;
    
    init(flags);
    int prime = 2;
    
    while (prime <= Math.sqrt(max)){
        crossOff(flags, prime);
        prime = getNextPrime(flags, prime);
    }
    return flags;
}

void crossOff(boolean[] flags, int prime){
    for(int i=prime*prime; i<flags.length; i+=prime){
        flags[i] = false;
    }
}

int getNextPrime(boolean[] flags, int prime){
    int next = prime + 1;
    while (next < flags.length && !flags[next]){
        next++;
    }
    return next;
}

 

 

[ 확률 ]

👀 A∩B의 확률

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

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

 

👀 A∪B의 확률

: P(A∪B) = P(A) + P(B) - P(A∩B)

 

👀 독립성

 A와 B가 한 사건의 발생과 다른 사건의 발생 사이에 아무런 관계가 없는 경우라면 A가 B에 아무런 영향을 끼치지 않으므로, P(B | A) = P(B)가 되고 따라서 P(A∩B) = P(A) P(B)가 됩니다.

 

👀 상호 배타성

 A와 B가 한 사건이 일어난 경우 다른 사건은 발생할 수 없는 경우라면, P(A∩B)=0이 되므로 P(A∪B)를 계산할 때 P(A∩B) 항은 제거해도 됩니다. 따라서 P(A∪B)=P(A)+P(B)가 됩니다.

 

⭐ 상호 배타성은 한 사건이 발생하면 다른 사건이 발생할 수 없다는 관계가 존재하지만 독립성은 한 사건의 발생 여부가 다른 사건에 아무런 영향도 미치지 않아야 하기 때문입니다. 그러므로 두 사건의 확률이 전부 0보다 클 경우엔, 상호 배타성과 독립성을 동시에 만족시킬 수는 없습니다.