[Java] 경우의 수

경우의 수

경우의 수란?

어떤 사건에서 일어날 수 있는 경우의 가짓수
ex1) 동전을 던지는 사건 : 경우의 수2
ex2) 주사위를 던지는 사건 : 경우의 수6

합의 법칙

• 사건A 또는 사건B가 일어날 경우의 수
• n(A ∪ B) = n(A) + n(B) - n(A ∩ B)

//두 개의 주사위를 던졌을 때 합이 3 또는 4의 배수일 경우

int[] dice1 = {1, 2, 3, 4, 5, 6};
int[] dice2 = {1, 2, 3, 4, 5, 6};

int nA = 0;
int nB = 0;
int nAandB = 0;

for (int item1: dice1) {
    for (int item2: dice2) {
        if ((item1 + item2) % 3 == 0) {
            nA +=1;
        }
        if ((item1 + item2) % 4 == 0) {
            nB += 1;
        }
        if ((item1 + item2) % 12 == 0) {
            nAandB +=1;
        }
    }
}
System.out.println("결과: " + ((nA + nB) - nAandB));   //20 출력

곱의 법칙

• 사건A와 사건B가 동시에 일어날 경우의 수
• n(A ∩ B) = n(A) x n(B)

//두개의 주사위 a, b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우

nA = 0;
nB = 0;
    for (int item1: dice1) {
        if(item1 % 3 == 0) {
            nA++;
        }
    }
    
    for (int item2: dice2) {
        if (item2 % 4 ==0) {
            nB++;
        }
    }
System.out.println("결과: " + nA * nB);

약수 구하기

public ArrayList getDivisor(int num) {
    ArrayList result = new ArrayList<>();
    for (int i = 1; i < (int)num / 2; i++) {
        if (num % i == 0) {
            result.add(i);
        }
    }
    result.add(num);
    return result;
}

최대 공약수(GCD: the Greatest Common Denominator) 구하기

public int getGCD(int numA, int numB) {
    int gcd = -1;
    
    ArrayList divisorA = this.getDivisor(numA);
    ArrayList divisorB = this.getDivisor(numB);
    
    for (int itemA: (ArrayList<Integer>)divisorA) {
        for (int itemB: (ArrayList<Integer>)divisorB) {
            if(itemA == itemB) {
                if (itemA > gcd) {
                    gcd = itemA;
                }
            }
        }
    }
    return gcd;
}

최소 공배수(LCM: the Lowest Common Multiple) 구하기

public int getLCM(int numA, int numB) {
    int lcm = -1;
    int gcd = this.getGCD(numA, numB);
    if (gcd != -1) {
        lcm = (numA * numB) / gcd;
    }
    return lcm;
}