[알고리즘 정리] 조합, 부분 집합 구현

 

 

다룰 내용

• 조합이란 무엇인가?
• 조합 구현
• 부분 집합이란 무엇인가?
• 부분 집합 구현

 

---

 

조합이란 무엇인가?

순서의 의미가 없이 수를 나열하는 것으로, 순열의 경우 순서가 의미가 있으나 조합은 의미가 없습니다.

 

 

조합을 구현하는 방법

1. 현재 자리에서 조합할 수를 선택합니다.

 

조합 구현 첫 번째 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Combination {

	public static int N, R;
	public static int origin[], number[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input[] = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		R = Integer.parseInt(input[1]);
		origin = new int[N];
		number = new int[R];
		
		String input2[] = br.readLine().split(" ");
		for(int i = 0; i < N; i++){
			origin[i] = Integer.parseInt(input2[i]);
		}
		
		combination(0, 0);
	}
	
	// 현재 위치에 조합할 수 선택
	private static void combination(int cnt, int idx) {
		if(cnt == R) {
			System.out.println(Arrays.toString(number));
			return;
		}
		
		for(int i = idx; i < N; i++) {
			number[cnt] = origin[i];
			combination(cnt + 1, i + 1);
		}
	}
}

 

 

조합 구현 두 번째 방법

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Combination2 {

	public static int N, R;
	public static int origin[], number[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input[] = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		R = Integer.parseInt(input[1]);
		origin = new int[N];
		number = new int[R];
		
		String input2[] = br.readLine().split(" ");
		for(int i = 0; i < N; i++){
			origin[i] = Integer.parseInt(input2[i]);
		}
		
		combination(0, 0);
	}
	
	// 현재 위치에 조합할 수 선택
	private static void combination(int cnt, int idx) {
		if(cnt == R) {
			System.out.println(Arrays.toString(number));
			return;
		}
		
		if(idx >= N) return;
		
		number[cnt] = origin[idx];
		combination(cnt + 1, idx + 1);
		combination(cnt, idx + 1);
	}
}

 

두 번째 방법은 현 위치에서 현재 원소를 선택하는 경우와 선택하지 않는 경우를 다 시도해보는 방법입니다.

 

---

 

부분 집합이란 무엇인가?

어떤 집합에 대해서 원소를 부분적으로만 가지는 것을 말합니다. 아무것도 가지지 않는 경우부터 모두 다 갖는 경우도 포함될 수 있습니다.

 

 

부분 집합을 구하는 방법

1. 처리하는 원소를 선택하는 경우와 선택하지 않는 경우로 나눠서 집합에 넣는 방식으로 구할 수 있습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Subset {

	public static int N, origin[];
	public static boolean isSelected[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		origin = new int[N];
		isSelected = new boolean[N];
		
		String input2[] = br.readLine().split(" ");
		for(int i = 0; i < N; i++){
			origin[i] = Integer.parseInt(input2[i]);
		}
		
		subset(0);
	}
	
	private static void subset(int cnt) {
		if(cnt == N) {

			for(int i = 0; i < N; i++) {
				System.out.print((isSelected[i] ? origin[i] : "X") + " ");
			}
			System.out.println();
			return;
		}
		
		isSelected[cnt] = true;
		subset(cnt + 1);
		
		isSelected[cnt] = false;
		subset(cnt + 1);
	}
}