기초 수학 - 경우의 수

1. 합의 법칙

• 경우의 수 = A 경우의 수 + B 경우의 수 - 공통 경우의 수

 

ex) 두 개의 주사위를 던졌을 때, 합이 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; // 3의 배수이면서 4의 배수

for (int i = 0; i < dice1.length; i++) {
    for (int j = 0; j < dice2.length; j++) {
        int sum = dice1[i] + dice2[j];
        
        // 3의 배수
        if (sum % 3 == 0) nA++;
        // 4의 배수
        if (sum % 4 == 0) nB++;
        
        // 공통 경우의 수
        if (sum % 12 == 0) nAandB++; // 공통 경우 빼야 함
    }
}

System.out.println("결과 = " + (nA + nB - nAandB));

 

🎲 HashSet 이용한 풀이

// HashSet은 중복을 허용하지 않기 때문에 중복제거가 자동으로 된다.
HashSet<ArrayList<Integer>> allCase = new HashSet<>();

for (int item1 : dice1) {
    for (int item2 : dice2) {
        if ((item1 + item2) % 3 == 0 || (item1 + item2) % 4 == 0) {
            ArrayList<Integer> pair = new ArrayList<>(Arrays.asList(item1, item2));
            allCase.add(pair);
        }
    }
}

System.out.println("HashSet 결과 = " + allCase.size());

 

2. 곱의 법칙

• A 사건이 일어나는 경우의 수 × B 사건이 일어나는 경우의 수

 

ex) 두 개의 주사위를 던졌을 때, 첫 번째 주사위는 3의 배수, 두 번째 주사위는 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));

 

// 곱의 법칙은 서로 독립적인 경우에 적용한다.

 

 

3. 최대공약수(GCD), 최소공배수(LCM)

 

🧩 약수 구하기

ArrayList<Integer> getDivisor(int num) {
    ArrayList<Integer> result = new ArrayList<>();
    // 자기 숫자의 절반
    for (int i = 1; i <= num / 2; i++) {
        if (num % i == 0) {
            result.add(i);
        }
    }
    result.add(num); // 자기 자신도 약수에 포함
    return result;
}

 

 

🧩 최대공약수(GCD) 구하기

 

int getGCD(int numA, int numB) {
    int gcd = -1;
    ArrayList<Integer> divisorsA = getDivisor(numA);
    ArrayList<Integer> divisorsB = getDivisor(numB);

    for (int itemA : divisorsA) {
        for (int itemB : divisorsB) {
        
        // 공약수를 구하고, gcd 변수와 비교하여 가장 큰 수 선별
            if (itemA == itemB && itemA > gcd) {
                gcd = itemA;
            }
        }
    }
    return gcd;
}

• 공통된 약수 중 가장 큰 값을 선택한다.

 

🧩 최소공배수(LCM) 구하기

int getLCM(int numA, int numB) {
    int lcm = -1;
    int gcd = getGCD(numA, numB);

    if (gcd != -1) {
        lcm = (numA * numB) / gcd;
    }
    return lcm;
}

• 공식: LCM = (A × B) ÷ GCD

Practice p = new Practice();
ArrayList<Integer> l1 = p.getDivisor(10);   // 1, 2, 5, 10
ArrayList<Integer> l2 = p.getDivisor(6);    // 1, 2, 3, 6

System.out.println("l1 = " + l1);
System.out.println("l2 = " + l2);

System.out.println("최대공약수 = " + p.getGCD(10, 6)); // 2
System.out.println("최소공배수 = " + p.getLCM(10, 6)); // 30

 

실행결과

l1 = [1, 2, 5, 10]
l2 = [1, 2, 3, 6]
최대 공약수: 2
최대 공배수: 30

 

 

정리

 

항목	공식	설명
최대공약수(GCD)	약수 중 가장 큰 값	유클리드 호제법을 사용하면 더 빠르게 구할 수 있다.
최소공배수(LCM)	(A × B) ÷ GCD	공약수를 이용해 효율적으로 계산 가능하다.