경우의 수 (합의 법칙, 곱의 법칙)

경우의 수

---

어떤 사건에서 일어날 수 있는 경우의 가짓수.

 

- 사건 A가 일어날 경우의 수 n(A)

 

 

합의 법칙

---

- A 또는 B가 일어날 경우의 수

- n(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;  //3의 배수
        int nB = 0;  //4의 배수
        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));

 

* HashSet 이용

  HashSet<ArrayList> allCase = new HashSet<>();
        for (int item1 : dice1) {
            for (int item2 : dice2) {
                if ((item1 + item2) % 3 == 0 || (item1 + item2) % 4 == 0) {
                    ArrayList list = new ArrayList(Arrays.asList(item1, item2));
                    allCase.add(list);
                }
            }
        }
         System.out.println("결과: " + allCase.size());

 

 

 

곱의 법칙

---

- A와 B가 동시에 일어날 경우의 수

- n(AxB)

- n(AxB) = n(A) X n(B)

        nA = 0;
        nB = 0;

        for (int item1 : dice1) {
            if (item1 % 3 == 0) {
                nA++;
            }

        }
        for (int item1 : dice2) {
            if (item1 % 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;
    }

 

 

 

최대 공약수

---

공통 약수 중 가장 큰 수

    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) {
                    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;
    }