[Java] 조합(Combination), 부분집합(Subset)

본 글에서는 java에서 조합과 부분집합을 작성하는 다양한 방법을 알아봅니다.

조합, 부분집합

조합

• n개의 수열에서 순서를 고려하지 않고 중복 없이 r개를 선택하는 것을 의미합니다.
• 위 문장을 수학적 기호로 나타내면 $nCr$입니다.
  
  

부분집합

• 주어진 집합의 모든 원소 중에서 일부 또는 전부를 포함하는 집합을 의미합니다.
• 순서를 고려하지 않으며, 선택된 원소의 개수에 제한이 없습니다.
  
  

실생활에서의 조합, 부분집합

• 조합, 부분집합은 생활속에서도 자주 접할 수 있는 개념입니다.

1. 복권 번호를 맞추기 위해 45개 숫자중 6개를 선택했다. - 조합
2. 앨범 정리를 위해 삭제할 사진들을 선택했다. - 부분 집합

• 코딩은 결국 실생활에 존재하는 문제를 컴퓨터의 언어로 바꾸어 전달하는 것입니다. 실생활에서 자주 접할 수 있는 조합, 부분 집합을 컴퓨터에게 어떻게 명령할지 나만의 코드 스니펫으로 잘 기억하고 있는 것은 코딩을 효율적으로 만들어줄 수 있습니다

조합 구현하기

반복문과 재귀, 그리고 조합

• 프로그래밍에서 모든 반복문은 재귀문으로, 모든 재귀문은 반복문으로 변환이 가능합니다.
• 그렇기 때문에 반복 처리가 필요한 경우 한 가지 방법으로만 구현할 수 있으나 상황에 맞게 유리한 방법을 선택해 구현하는 것이 효율적입니다.
• 반복 문을 사용할지 재귀를 사용할지 판단하는 기준은 보통 다음과 같습니다.

반복문 사용 → 반복문이 몇 번 중첩되는지 알며, 그 중첩의 깊이가 깊지 않을 때
재귀 사용 → 반복문의 중첩 깊이가 동적일 때

• 조합은 일반적으로 재귀를 사용해 구현합니다. n개의 원소 중 몇 개의 원소를 선택할지 정해지지 않은 문제상황이 있기 때문입니다. 또한 안다고 하더라도 5개의 원소를 선택한다면? 아래와 같이 5중 반복문을 작성해야합니다.

// 원소를 뽑을 수열
int[] nums = {1, 2, 3, 4, 5, 6, 7};

// nums로부터 5개를 뽑아 조합을 구성할 배열
int[] combination = new int[5];

for (int i = 0; i < nums.length; ++i) {
combination[0] = nums[i];

	for (int j = i + 1; j < nums.length; ++j) {
    	combination[1] = nums[j];

    	for (int k = j + 1; k < nums.length; ++k) {
        	combination[2] = nums[k];

        	for (int l = k + 1; l < nums.length; ++l) {
            	combination[3] = nums[l];

            	for (int m = l + 1; m < nums.length; ++m) {
                	combination[4] = nums[m];
                	System.out.println(Arrays.toString(combination));
            	}
        	}
    	}
	}
}

• 그래도 중복체크를 해야 하는 순열에 비해서는 사정이 조금 낫지만 피장파장입니다. 보는 순간 현기증이 나려 합니다.
  
  

java에서 전형적인 조합코드

import java.io.*;
import java.util.*;

class Main {
	static List<Integer> input = new ArrayList<>(); // 입력받은 수의 집합
	static int n, r;
	
	static int count;
	static int[] data;  // 조합으로 뽑은 데이터
	
	// index번째 원소를 뽑아 조합을 구성한다.
	static void combination(int index, int checked) {
    	
        // index가 r에 다다르면 원하는 행위를 한다.
		if (index == r) {
			
			count++;
			System.out.println("#" + count + " " + Arrays.toString(data));
			
			return;
		}
		
        // index번째 원소를 뽑는다.
        // 이미 뽑았거나, 뽑지 않기로 결정한 원소들(check 이전 원소들)은 후보에서 제외
		for (int i = checked; i < n; ++i) {
			data[index] = input.get(i);
			combination(index + 1, i + 1);
		}
	}
	
	public static void main(String[] args) throws Exception {
		System.out.println("nCr 출력 프로그램");
		
		// 수열 입력
		System.out.print("수열 입력: ");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		while (st.hasMoreTokens()) {
			input.add(Integer.parseInt(st.nextToken()));
		}
		
		// r 입력 및 변수 초기화
		System.out.print("r 입력: ");
		r = Integer.parseInt(br.readLine());
		
		n = input.size();
		data = new int[r];
		
		combination(0, 0);
	}
}

주의

• 조합을 외우고 심취한 나머지 $nC2$인 경우가 발생했을 때 어렵게 재귀를 통해 구현하고 있지는 않은가요?
• $nC2$는 이중 for문이면 충분합니다.

for (int i = 0; i < n; ++i) {
	for (int j = i + 1; j < n; ++j) {
		int firstNum = nums[i];
        int secondNum = nums[j];
        
        // 원소를 뽑았을 때의 처리
    }
}

• 경우에 따라 $nC3$ 또한 삼중 for문이 구현의 편의성 및 코드의 직관적 이해에 유리할 수 있으므로 상황에 맞게 좋은 방법을 사용합시다!
  
  

부분집합 구현

조합으로 부분집합 구현

• 부분집합은 0개 원소를 뽑은 조합 + 1개 원소를 뽑은 조합 + ... + n개 원소를 뽑은 조합으로 나타낼 수 있습니다.

import java.io.*;
import java.util.*;

class Main {
	static List<Integer> input = new ArrayList<>(); // 입력받은 수의 집합
	static int n, r;
	
	static int count;
	static int[] data;  // 조합으로 뽑은 데이터
	
	// index번째 원소를 뽑아 조합을 구성한다.
	static void combination(int index, int checked) {
		
		// index가 r에 도달하면 하나의 조합이 완성된 것이다.
		if (index == r) {
			
			// 하나의 부분집합이 완성되었을 때의 처리
			count++;
			System.out.println("#" + count + " " + Arrays.toString(data));
			
			return;
		}
		
		for (int i = checked; i < n; ++i) {
			data[index] = input.get(i);
			combination(index + 1, i + 1);
		}
	}
	
	public static void main(String[] args) throws Exception {
		System.out.println("부분집합 출력 프로그램");
		
		// 수열 입력
		System.out.print("수열 입력: ");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		while (st.hasMoreTokens()) {
			input.add(Integer.parseInt(st.nextToken()));
		}
		
		// 수열로부터 0 ~ n 개의 원소 조합을 선택하는 경우 = 부분집합
		n = input.size();
		for (int i = 0; i <= n; ++i) {
			r = i;
			data = new int[r];
			combination(0, 0);
		}
	}
}

재귀로 부분집합 구현

• 보다 간단하게 i 번째 원소를 선택할지, 말지 2가지로 분기하는 재귀 함수로 구현할 수 있습니다.

import java.io.*;
import java.util.*;

class Main {
    static List<Integer> input = new ArrayList<>(); // 입력받은 수의 집합
    static int n;

    static int count;
    static List<Integer> data = new ArrayList<>();  // 부분집합

    // index번째 원소를 뽑아 조합을 구성한다.
    static void subset(int index) {

        // index가 n에 도달하면 하나의 부분집합이 완성된 것
        if (index == n) {

            // 하나의 부분집합이 완성되었을 때의 처리
            count++;
            System.out.println("#" + count + " " + data);

            return;
        }

        subset(index + 1);
        data.add(input.get(index));
        subset(index + 1);
        data.remove(data.size() - 1);
    }

    public static void main(String[] args) throws Exception {
        System.out.println("부분집합 출력 프로그램");

        // 수열 입력
        System.out.print("수열 입력: ");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            input.add(Integer.parseInt(st.nextToken()));
        }

        n = input.size();

        // 부분집합 구하기
        subset(0);
    }
}

비트마스킹 기법으로 구현

• 부분집합을 구현하는 방법 중 비트 마스킹을 이용한 재미있는 방법이 있어 소개합니다.
• int[] nums = {1, 2, 3} 의 모든 부분집합을 구하고 부분집합에 원소가 속해있으면 1, 속하지 않는다면 0을 표시해 보았습니다.
  
• 혹시 어떤 규칙이 느껴지시나요? 잘 모르겠다면 순서를 한 번 바꿔보겠습니다.
  
• 표 안의 숫자는 0부터 7까지의 숫자를 이진법으로 나타낸 결과입니다.
• 이처럼 원소가 n 개인 집합으로부터 부분집합을 구할 때, 특정 위치의 원소가 어떤 부분집합에 속해있는지를 0 또는 1로 나타내보면 0부터 $2^n - 1$ 까지의 정수가 이진법으로 모두 적혀있는 것을 확인할 수 있습니다.
• 이를 이용하여 부분집합을 다음과 같이 구현할 수 있습니다.

import java.io.*;
import java.util.*;

class Main {
    static List<Integer> input = new ArrayList<>(); // 입력받은 수의 집합
    static int n;

    static int count;

    // index번째 원소를 뽑아 조합을 구성한다.
    static void subset() {
        for (int mask = 0; mask < (1 << n); ++mask) {
            List<Integer> temp = new ArrayList<>();

            // mask는 각 원소의 포함 여부를 0 또는 1로 나타낸 숫자
            for (int j = 0; j < n; ++j) {
                if ((mask & 1 << j) != 0)
                    temp.add(input.get(j));
            }

            // 하나의 부분집합이 완성되었을 때의 처리
            count++;
            System.out.println("#" + count + " " + temp);
        }
    }

    public static void main(String[] args) throws Exception {
        System.out.println("부분집합 출력 프로그램");

        // 수열 입력
        System.out.print("수열 입력: ");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            input.add(Integer.parseInt(st.nextToken()));
        }

        n = input.size();

        // 부분집합 구하기
        subset();
    }
}

마무리하며

• Java에서 조합과 부분집합을 구현하는 다양한 방법을 알아보았습니다. 각 방법은 특정 상황에 따라 그 효율성과 적합성이 달라질 수 있습니다. 반복문, 재귀, 그리고 비트 마스킹을 상황에 맞게 적절히 활용하는 것이 중요합니다.
• java에는 조합, 부분집합을 간단히 지원해 주는 내장 모듈이 존재하지 않습니다. 간단히 연습해 보시고 여러분의 프로그래밍에 유용한 도구가 되면 좋겠습니다.