[JAVA] 순열, 조합, 부분집합, 중복순열, 중복조합 (순조부)

🔍 완전 탐색

완전 탐색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법입니다.

코딩 테스트 문제를 풀 때, 우선 완전 탐색으로 접근하여 답을 찾고, 성능 개선을 위해 다른 알고리즘을 사용하며 시간과 메모리를 줄여나가는 것이 좋습니다.

보통 순열, 조합, 부분집합과 같은 조합적 문제와 함께 푸는 문제들이 많이 출제되는데, 

만약 조합된 결과에 순서가 의미가 있다면 순열, 순서가 의미가 없다면 조합, 선택하는 개수가 고정되지 않고 상황에 따라 다르다면 부분집합을 사용합니다.

 

🔍 순열 (permutation), 중복순열

순열은 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것입니다. 즉, 서로 다른 n개중 r개를 택하는 것이죠!(nPr)순열은 팩토리얼과 연관되어있는데, 만약 n이 12를 넘어가면 12! 이 470,001,600이므로 n이 12를 넘어가면서 시간 복잡도가 폭발적으로 증가합니다. 주의해서 사용하시길 바랍니다!

 

중복순열일 경우, 순열 코드에서 기존 자릿수들과 중복되는지 체크하는 isSelected배열을 제거한다면 같은 수도 중복해서 뽑을 수 있는 중복순열의 코드가 됩니다.

 

재귀를 통한 순열 생성 방법은 다음과 같습니다.

static int N, R;
static int[] input, numbers; //input : 입력수배열, numbers : 선택수배열
static boolean[] isSelected;

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	R = sc.nextInt();
	
	input = new int[N];
	numbers = new int[R];
	isSelected = new boolean[N];
	
	for(int i=0;i<N;i++) {
		input[i] = sc.nextInt();
	}
	permutation(0);
}

// 메소드 정의 : 현재 자리에 수를 뽑기
public static void permutation(int cnt) { //cnt : 직전까지 뽑은 수의 개수
	
	//기본파트
	if(cnt == R) {
		System.out.println(Arrays.toString(numbers));
		return;
	}
	
	//입력받은 모든 수를 현재 자리에 넣어보기
	for(int i = 0; i<N;i++) {
		//기존 자리의 수들과 중복되는지 체크
		if(isSelected[i]) continue;
		
		//중복되지 않았다면 사용함
		numbers[cnt] = input[i];
		isSelected[i] = true;
		//다음 수 뽑으러 가기
		permutation(cnt+1);
		isSelected[i] = false;
	}
}

 

🔍 조합 (combination), 중복 조합

조합은 순열과 다르게 순서가 중요하지 않습니다. 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것이죠!(nCr)조합은 isSelected배열이 없어지고 매개변수로 start변수가 추가됩니다.

 

중복 조합의 경우, 기존 조합 코드의 inductive part에서 재귀 코드를 부르며 combination(cnt+1, i+1)의 코드를 combination(cnt+1, i)로 설정할 경우, 현재 뽑은 자리도 다시 탐색하기 때문에 중복 조합을 구현할 수 있습니다.

static int N, R;
static int[] input, numbers; //input : 입력수배열, numbers : 선택수배열

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	R = sc.nextInt();
	
	input = new int[N];
	numbers = new int[R];
	
	for(int i=0;i<N;i++) {
		input[i] = sc.nextInt();
	}
	combination(0, 0);
}

public static void combination(int cnt, int start) {
	if(cnt == R) {
		System.out.println(Arrays.toString(numbers));
		return;
	}
	
	for(int i=start;i<N;i++) {
		numbers[cnt] = input[i];
		combination(cnt+1, i+1); //다음 자리는 현재 뽑은 i의 다음수부터 시작하도록 전달
	}
}

 

🔍 부분집합 (generateSubset)

부분집합은 선택하는 개수가 고정되지 않고, 상황에 따라 다른 집합입니다. 

부분집합의 개수와 관련해서 설명드리겠습니다.

1. 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 개수는 2^n개입니다. 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우의 수와 같습니다.

2. n이 30이면 부분집합의 개수가 2^30이 넘어가므로 시간 복잡도가 너무 커서 부분집합으로 풀기 어렵습니다.

부분집합 또한 재귀적으로 구현한 코드입니다.

static int N, input[];
static boolean[] isSelected;

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);	
	N = sc.nextInt();
	input = new int[N];
    
	isSelected = new boolean[N];
	for(int i=0;i<N;i++) {
		input[i] = sc.nextInt();
	}
    
	generateSubset(0);
}

public static void generateSubset(int cnt) { //부분집합에 고려해야 하는 원소, 직전까지 고려한 원소 수
	
	if(cnt==N) {  //마지막 원소까지 부분집합에 다 고려된 상황
		for (int i = 0; i < N; i++) {
			System.out.print((isSelected[i]? input[i] : "X")+" ");
		}
		System.out.println();
		return;
	}
	
	//현재 원소를 선택
	isSelected[cnt] = true;
	generateSubset(cnt+1);
	//현재 원소를 비선택
	isSelected[cnt] = false;
	generateSubset(cnt+1);
}

 

위와 같이 기저 조건인 base part와 재귀를 부르는 inductive part를 나누어 구현하면 쉽게 순열, 조합, 부분집합 코드를 구현할 수 있었습니다!