Algorithm with Math - 순열, 조합

 

GCD/LCM(최대공약수, 최소공배수)
순열/조합
멱집합

 

 

 

순열(permutation)과 조합(Combination)

 

 

순열: 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수.
조합 : 순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수.

 

🎪 카드 뽑기

5장의 카드 중 순서를 고려하고, 혹은 고려하지 않고 3장을 뽑을 때의 경우의 수는?

 

1. 순열(P ; Permutation)

nPɾ = n! / (n - r)!
5 X 4 X 3 = 60가지의 방법

 

• 첫 번째 나열하는 카드를 선택하는 방법: 다섯 가지
• 첫 번째 카드를 나열하고, 두 번째 카드를 선택하는 방법: 네 가지
• 두 번째 카드를 나열하고, 세 번째 카드를 선택하는 방법: 세 가지

[A, B, D]와 [A, D, B]는 나열하는 순서가 다르므로 서로 다른 경우이다

        String[] lookup = new String[]{"A", "B", "C", "D", "E"};
        ArrayList<String[]> result = new ArrayList<>();

        for (int i = 0; i < lookup.length; i++) {
            for (int j = 0; j < lookup.length; j++) {
                for (int k = 0; k < lookup.length; k++) {

                    //중복 요소를 허용하지 않는다
                    if (i == j || j == k || k == i) continue;
                    String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
                    result.add(input);
                }
            }
        }

 

2. 조합(C ; Combination)

nCɾ = n! / ((n - r)! * r!)   →   nPɾ에서 줄 세우는 방법 취소함!
(5 X 4 X 3 X 2 X 1) / ((3 X 2 X 1) X (2 X 1)) = 10가지 방법

nPɾ = nCɾ * r!   →   뽑고, 줄 세운다!

 

3장을 하나의 그룹으로 선택하기

• 순열로 구할 수 있는 경우를 찾는다
• 순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눈다

[A, B, D]와 [A, D, B]는 하나의 경우이다

 

조합

String[] lookup = new String[]{"A" , "B", "C", "D", "E"};
ArrayList<String[]> result = new ArrayList<>();

//한 번 조합한 요소는 다시 조합하지 않는다
//하나의 요소로 만들 수 있는 모든 경우의 수를 다 구한 다음,
// 그 요소를 반복에 포함하지 않고 다음 요소부터 시작한다
for (int i = 0; i < lookup.length; i++) {
    for (int j = i + 1; j < lookup.length; j++) {
        for (int k = j + 1; k < lookup.length; k++) {

            String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
            result.add(input);
        }
    }
}

 

중복 조합

private static void combination(int r, int[] temp, int current, int start) {

    //뽑고자 하는 개수 == 현재 개수
    if (r == current) {
        System.out.println(Arrays.toString(temp));
    }
        
    else {
        for (int i = start; i < arr.length; i++) {
            //요서의 i번째 값을 결과값 배열 temp에 담는다
            temp[current] = arr[i];
            makeCombination(r, temp, current + 1, i + 1);
        }
    }
}

 

반복문으로 순열과 조합 만들기의 한계

• 뽑아 낼 개수가 늘어나면 반복문의 수도 늘어난다
• 뽑아 낼 개수가 사전에 정의되어 있지 않으면 대응하기 어렵다

재귀를 이용하여 풀이한다!

 

 

문제 유형

 

🌿 소수 찾기

한 자리 숫자가 적힌 종잇조각이 흩어져 있습니다.
흩어진 종잇조각을 붙여 만들 수 있는 소수의 개수는 무엇인가요?
종이에 기록된 모든 숫자는 배열로 주어집니다.

 

나열 순서가 다르면 다른 숫자이므로 순열로 접근한다

1. n개의 숫자 중에 1~k개를 뽑아서 순열을 생성한다
2. 각 순열을 정수로 변환하고, 해당 정수가 중복되지 않으면서 동시에 소수인지 검사한다
3. 소수라면 개수를 센다

 

🌿 일곱 난쟁이

백설 공주에게 위기가 찾아왔습니다.
하루 일과를 마치고 돌아온 "일곱" 난쟁이가 "아홉"명이었던 겁니다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했습니다.
백설 공주는 일곱 난쟁이의 키의 합이 100임을 기억해 냈습니다.
아홉 난쟁이 각각의 키가 주어질 때, 일곱 난쟁이를 찾는 방법은 무엇인가요?

 

순서를 생각하지 않고(조합), 9명의 난쟁이 중 7명의 난쟁이의 키를 합했을 때 100이 되는 경우를 찾는다