[기타] 자바로 조합 구현하기(with 공주 옷입히기)

[01. 조합]

조합은 N개의 숫자가 있으면 몇개(R)뽑니? 순서는 상관 없단다!

항상 순열과 조합이 했갈렸는데, 순열 : 순서생각해서 나열, 조합은 조건없이 합침 이런 느낌으로 구별하는 듯 싶다..

 

그래서 조합은 ?

초등학교때 옷입기 조합을 만들어 본 적이 있을 것이다.. 그거랑 비슷하게 공주님 옷 입히기를 해보겠다

flaticon에서 가지고 온 드레스들입니다.

조합은 순서가 상관이 없어서 겹치는걸 다 빼준다는 이야기라고 생각하면 쉽다

신발을 먼저 고르고, 드레스를 먼저 고르냐 ->  드레스를 먼저 고르고 신발을 먼저 고르냐... 같은 이야기지 않습니까 ?

조합은 옷입히기다! 라고 생각합니다.

 

그래서 코드로는 어떻게 구현하냐.. 

public class MakeCombination {
    public static void main(String[] args) {
        String[] dresses = {"분홍원피스", "노랑원피스", "정렬의 래드", "시크한 블랙"};
        String[] shoes = {"유리구두", "분홍꽃신", "검정하이힐"};

        combination(dresses, shoes);
    }

    public static void combination(String[] dresses, String[] shoes) {
        // 각 드레스마다 하나의 신발만을 고려하여 조합을 출력
        int count = 0;
        for (String dress : dresses) {
            for (String shoe : shoes) {
                System.out.println(dress + " + " + shoe);
                count++;
            }
        }
        System.out.println("조합의 수는 ? " + count);
    }
}

 출력은 다음과 같이 나온다

---

그렇다면 조금 더 나아가 예제를 하나 가지고왔다

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

부분집합의 합이 원하는수! 가 되는 로직이지만, 

나는 조금 변경시켜 부분집합을 출력할 수 있게 코드를 짜 보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BJ_1182_부분수열의합2 {

    static int N;
    static int S;
    static int count = 0;
    static int[] array;
    static ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 정수의 개수
        N = Integer.parseInt(st.nextToken());
        // 조합해서 나올 수
        S = Integer.parseInt(st.nextToken());
        // 담아둘 array
        array = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int  i = 0; i < N; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        generateSubsequences(array, 0, new ArrayList<Integer>(), result);


        for (ArrayList<Integer> subsequence : result) {
            System.out.println(subsequence);
        }

        /**
         * 출력
         * []
         * [8]
         * [5]
         * [5, 8]
         * [-2]
         * [-2, 8]
         * [-2, 5]
         * [-2, 5, 8]
         * [-3]
         * [-3, 8]
         * [-3, 5]
         * [-3, 5, 8]
         * [-3, -2]
         * [-3, -2, 8]
         * [-3, -2, 5]
         * [-3, -2, 5, 8]
         * [-7]
         * [-7, 8]
         * [-7, 5]
         * [-7, 5, 8]
         * [-7, -2]
         * [-7, -2, 8]
         * [-7, -2, 5]
         * [-7, -2, 5, 8]
         * [-7, -3]
         * [-7, -3, 8]
         * [-7, -3, 5]
         * [-7, -3, 5, 8]
         * [-7, -3, -2]
         * [-7, -3, -2, 8]
         * [-7, -3, -2, 5]
         * [-7, -3, -2, 5, 8]
         * */

    }

    public static void generateSubsequences(int[] nums, int index, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result) {
        if (index == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        // 현재 인덱스의 원소를 포함하지 않는 경우
        generateSubsequences(nums, index + 1, current, result);

        // 현재 인덱스의 원소를 포함하는 경우
        current.add(nums[index]);
        generateSubsequences(nums, index + 1, current, result);

        // Backtrack
        current.remove(current.size() - 1);
    }


}

 

예제에서 주어진 배열이 [ -7, -3, -2, 5, 8] 인데, 

모든 경우의 수를 탐색하기 위해 재귀를 사용하였습니다.

맨 먼저 출력이 공집합[]이 나오는 이유는 index 가 0번부터 시작하는데,

첫번째 원소를 아무것도 선택하지 않는 경우가 포함되어 있기 때문입니다... 그럼 텅 빈 공집합이 나오겠죠?

 

+ 이제 재귀호출이 되니까 다음 인덱스부터 시작을 하게 됩니다.. 그래서 8이 나오는 것이죠

그렇게 차례차례 돌면서 result 값을 arrayList에 추가해줍니다. 한번에 출력하기 위해서죠

 

+ 자 이제 여기서 정답처리를 해 주려면 sum이 S 일때만 로직을 추가해 주면 됩니다.

public static void generateSubsequences(int index, int sum) {
        if (index > 0 && sum == S) {
            count += 1;
        }
        
        // 즉 실행은 여기부터
        for (int i = index; i < N; i++) {
            // 다음 원소를 포함시킨 새로운 합으로 재귀 호출
            generateSubsequences(i + 1, sum + array[i]);

        }
    }

 

오히려 조건이 더 간단해졌어요.. sum이 S가 되면!  count 변수에 저장해두었다가 꺼내쓰기!

이상입니다!