경우의 수

경우의 수

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

- 예시 1) 동전을 던지는 사건: 경우의 수 2

- 예시 2) 주사위를 던지는 사건: 경우의 수 6

 

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

---

합의 법칙

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

→ 사건 A와 사건 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∪B) = n(A) + n(B) - n(A∩B)

→ 12 + 9 -1 = 20

---

곱의 법칙

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

→ 사건 A와 사건 B의 곱의 법칙: n(AxB)

 

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

 

* 사건 A: a가 3의 배수일 경우

2가지: 3, 6

 

* 사건 B: b가 4의 배수일 경우

1가지: 4

 

n(AxB) = n(A) x n(B)

→ 2 x 1 = 2

---

실습 코드

// 기초 수학 - 경우의 수

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

public class Main {
    public static void main(String[] args) {

//      1. 합의 법칙
        System.out.println("== 합의 법칙 ==");
//      두 개의 주사를 던졌을 때 합이 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; // 공통된 부분

        /* 기본 풀이
         주사위 2개를 for문으로 돌면서
         두 주사위 눈금의 합이 3의 배수일 경우 nA 1씩 증가
         마찬가지 nB 1씩 증가, nAandB 1씩 증가
        */
        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 이용
        /* 기본 풀이는 딱 숫자만 나왔다면,
        ArrayList는 주사위 눈금 (1, 2), (2, 1) 와 같은 데이터를 모두 저장할 수 있게 만들어주기 위함
         */
        HashSet<ArrayList> allCase = new HashSet<>();

        for(int item1 : dice1) {
            for(int item2 : dice2) {
                if((item1 + item2) % 3 == 0 || (item1 + item2) % 4 ==0) {
                    /* 주사위 2개의 숫자를 list로 만든 다음 HashSet에 넣어주면
                    모든 주사위 숫자 정보를 기록할 수 있고, HashSet을 이용해 add를 시키니깐
                    중복된 수는 알아서 빠짐
                    */
                    ArrayList list = new ArrayList(Arrays.asList(item1, item2));
                    allCase.add(list);
                }
            }
        }
        System.out.println("결과: " + allCase.size());

//      2. 곱의 법칙
        System.out.println("== 곱의 법칙 ==");
//      두 개의 주사위 a, b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우의 수
        nA = 0;
        nB = 0;

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

    }
}

---

약수 구하기

4의 약수 : 1, 2, 4

6의 약수 : 1, 2, 3, 6

최대공약수 : 2

최소공배수 : 12

빠른 계산 → 4x6 / 2(최대공약수)

// Practice
// 약수 구하기, 두 수의 최대공약수와 최소공배수 구하기
// 활용) 1~10의 수 중 A의 약수 또는 B의 약수인 경우의 수
// 활용) 1~10의 수 중 A의 약수이면서 B의 약수인 경우의 수

import java.util.ArrayList;

public class Practice {

    //  약수
    public ArrayList getDivisor(int num) {
        ArrayList result = new ArrayList();

        // num/2 -> 자기 수의 절반까지만 for문을 돌린다. (나누어서 떨어지는 수를 구하면 되니깐)
        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) {
                    // 그리고 그 약수가 gcd 값보다 크다면 계속해서 큰 공약수로 바꿔주기
                    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);


        // ex) 두 수 0, 5라면 최대공약수가 없으니깐 -1이 나오니깐
        // 예외적인 상황을 피하기 위해 gcd != -1로 지정
        if(gcd != -1) {
            lcm = numA * numB / gcd;
        }
        return lcm;
    }

    public static void main(String[] args) {

//      Test code
        int number1 = 10;
        int number2 = 6;

        Practice p = new Practice();
        ArrayList l1 = p.getDivisor(number1);   // 10: 1, 2, 5, 10
        ArrayList l2 = p.getDivisor(number2);   // 6: 1, 2, 3, 6
        System.out.println("l1 = " + l1);
        System.out.println("l2 = " + l2);

        System.out.println("최대 공약수: " + p.getGCD(number1, number2));
        System.out.println("최소 공배수: " + p.getLCM(number1, number2));
    }
}