기초수학 - 경우의 수 : 합의법칙, 곱의법칙, 약수, 최대공약수, 최소공배수)

경우의 수.

어떤 사건에서 일어날 수 있는 경우의 가짓수로
동전을 던졌을 때 나올 수 있는 가짓수는 2,
주사뤼를 던졌을 때 나올 수 있는 가짓누는 6이다.
사건 A가 일어날 경우의수는 n(A)로 표기하고
크게 순열, 조합, 중복순열 등이 있다.

경우의 수는 주어진 문제나 상황에 따라 다양한 방법으로 계산될 수 있고
게임 이론, 알고리즘 설계, 조합 최적화, 확률과 통계 등 다양한 분야에서 사용된다.

 

합의 법칙.

합의 법칙은 두 개 이상의 상호 배반적인 사건(이벤트)의 경우의 수를 더하여 전체 경우의 수를 계산하는 원리다.
즉, 두 사건이 동시에 발생하지 않을 때, 두 사건 중 하나가 발생하는 경우의 수는각각의 경우의 수를 더하여 구할 수 있으며
사건 A 또는 사건 B가 일어날 경우의 수는 합집합으로 표기할 수 있다.

어떤 행사에 A와 B 두 개의 부스가 있다고 가정하고
A 부스에서는 3가지 상품을 제공하고, B 부스에서는 4가지 상품을 제공한다고 하면,
이 행사에서 어느 부스에서든지 상품을 선택하는 경우의 수는
A 부스의 경우의 수(3)와 B 부스의 경우의 수(4)를 더한 값인 7이 된다.

// 사건 A와 사건 B의 합의 법칙 n(A ∪ B)
// n(A ∪ B) = n(A) + n(B) - n(A ∩ B)

// 두 개의 주사위를 던졌을 때 합이 3 또는 4의 배수일 경우의 수
// 사건 A : 합이 3의 배수인 경우
3 : (1, 2), (2, 1) 
6 : (1, 5), (2, 4), (3, 3), (4, 2), (5, 1)
9 : (3, 6), (4, 5), (5, 4), (6, 3)
12 : (6, 6)

// 사건 B : 합이 4의 배수인 경우
4 : (1, 3), (2, 2), (3, 1)
8 : (2, 6), (3, 5), (4, 4), (5, 3), (6, 2)
12 : (6, 6)

// n(A) + n(B) - n(A ∩ B)
// 12 + 9 - 1 = 20

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class SumMultiplicationRuleTest {
    public static void main(String[] args) {
        // 합의 법칙
        int[] diceA = {1, 2, 3, 4, 5, 6};
        int[] diceB = {1, 2, 3, 4, 5, 6};
        int nA = 0;
        int nB = 0;
        int nAandB = 0;

        // 반복문 이용하기
        for (int a : diceA) {
            for (int b : diceB) {
                if ((a + b) % 3 == 0) { // 두 주사위 합이 3의 배수인 경우의 수
                    nA += 1;
                }
                if ((a + b) % 4 == 0) { // 두 주사위 합이 4의 배수인 경우의 수
                    nB += 1;
                }
                if ((a + b) % 12 == 0) { // 두 주사위 합이 3과 4의 배수가 되는 경우의 수
                    nAandB += 1;
                }
            }
        }
        System.out.println(nA + nB - nAandB); // 20

        // HashSet 이용하기
        HashSet<ArrayList<Integer>> allCase = new HashSet<>();
        for (int a : diceA) {
            for (int b : diceB) {
                if ((a + b) % 3 == 0 || (a + b) % 4 == 0) {
                    ArrayList<Integer> list = new ArrayList<>(Arrays.asList(a, b));
                    allCase.add(list);
                }
            }
        }
        System.out.println(allCase.size()); // 20
        System.out.println(allCase);
        // [[2, 1], [5, 4], [2, 2], [3, 3], [4, 4], [6, 6],
        // [1, 2], [4, 5], [1, 3], [2, 4], [3, 5], [3, 6],
        // [1, 5], [2, 6], [5, 1], [6, 2], [6, 3], [3, 1],
        // [4, 2], [5, 3]]
    }
}

곱의 법칙.

곱의 법칙은 두 개 이상의 독립적인 사건의 경우의 수를 곱하여 전체 경우의 수를 계산하는 원리로
두 사건이 동시에 발생할 때, 각각의 경우의 수를 곱하여 구할 수 있다.
사건 A와 사건 B가 동시에 일어날 경우의 수는 n(A X B)로 표기할 수 있다.

주머니에 빨간 공과 파란 공이 들어있다고 가정하고 빨간 공이 4개이고 파란 공이 3개라면,
두 개의 공을 동시에 뽑을 때 빨간 공과 파란 공의 경우의 수는 빨간 공의 경우의 수(4)와 파란 공의 경우의 수(3)를 곱한 값인 12가 된다.

// 사건 A와 사건 B의 곱의 법칙
// n(A X B) = n(A) X n(B)

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

// 사건 B : b가 4의 배수인 경우
B : 4

// 2 X 1 = 2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class SumMultiplicationRuleTest {
    public static void main(String[] args) {
        // 합의 법칙
        int[] diceA = {1, 2, 3, 4, 5, 6};
        int[] diceB = {1, 2, 3, 4, 5, 6};
        int nA = 0;
        int nB = 0;

        // 곱의 법칙
        nA = 0;
        nB = 0;

        for (int a : diceA) {
            if (a % 3 == 0) { // a 가 3의 배수 일 때
                nA += 1;
            }
        }
        for (int b : diceB) {
            if (b % 4 == 0) { // b가 4의 배수 일 때
                nB += 1;
            }
        }
        System.out.println(nA * nB); // 2
    }
}

 

 

약수,  최대 공약수,  최소 공배수.

약수 (Divisor)
어떤 자연수를 나누어 떨어지게 하는 수를 그 자연수의 약수라고 한다.
6의 약수는 1, 2, 3, 6

최대 공약수 (Greatest Common Divisor, GCD)
두 개 이상의 자연수의 공통된 약수 중에서 가장 큰 수를 최대 공약수라고 한다.
12와 18의 최대 공약수는 6입니다.

최소 공배수 (Least Common Multiple, LCM):
두 개 이상의 자연수의 공통된 배수 중에서 가장 작은 수를 최소 공배수라고 한다.
4와 6의 최소 공배수는 12이며 이는 두 수의 곱과 최대 공약수를 나누면 된다.

import java.util.ArrayList;

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

    // 최대 공약수
    public int getGCD(int a, int b) {
        int gcd = -1;
        ArrayList<Integer> divisorA = this.getDivisor(a);
        ArrayList<Integer> divisorB = this.getDivisor(b);

        for (int itemA : divisorA) {
            for (int itemB : divisorB) {
                if (itemA == itemB) {
                    if (itemA > gcd) {
                        gcd = itemA;
                    }
                }
            }
        }
        return gcd;
    }

    // 최대 공약수 (유클리드 호제법)
    public int findGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // 최소 공배수
    public int getLCM(int a, int b) {
        int lcm = -1;
        int gcd = this.getGCD(a, b);
        if (gcd != -1) {
            lcm = a * b / gcd;
        }

        return lcm;
    }

    public static void main(String[] args) {
        int numberA = 10;
        int numberB = 6;

        CommonNumberTest ct = new CommonNumberTest();
        ArrayList<Integer> listA = ct.getDivisor(numberA);
        ArrayList<Integer> listB = ct.getDivisor(numberB);
        // 약수
        System.out.println(listA); // [1, 2, 5, 10]
        System.out.println(listB); // // [1, 2, 3, 6]

        // 최대 공약수, 최소 공배수
        System.out.println(ct.findGCD(numberA, numberB)); // 2
        System.out.println(ct.getGCD(numberA, numberB)); // 2
        System.out.println(ct.getLCM(numberA, numberB)); // 30
    }
}