[JAVA] 순열, 조합, 부분집합 (순조부) 알고리즘 코드 완전 정리

 

조금이라도 문제를 풀지 않으면 바로 까먹어버리는 기본 중의 기본 이른바 순조부를 까먹지 않기 위해 한 곳에 모아서 정리하고자 한다 ㅎㅎ

 

아래는 배열 {1, 2, 3, 4, 5} 중 3개를 뽑는 순열, 중복순열, 조합, 중복조합 코드이다.

 

 

 

---

 

순열

 

import java.util.*;

public class Perm {
	static int n; //뽑아야 하는 수의 개수
	static int[] num; //뽑은 숫자를 저장하는 배열
	static int[] arr; //뽑을 숫자가 담긴 배열
	static boolean[] select; //index에 해당하는 숫자가 사용됐는지 저장하는 배열
	
	public static void main(String[] args) {
		arr = new int[5];
		
		for (int i = 0; i < 5; i++)
			arr[i] = i + 1; //1,2,3,4,5 저장
		
		n = 3;
		num = new int[3]; //5개 중 3개를 뽑아 순열 만들기
		select = new boolean[5];
		
		perm(0);
	}
	
	public static void perm(int cnt) {//순열 코드
		if (cnt == n) {
			System.out.println(Arrays.toString(num));
			return;
		}
		
		for (int i = 0; i < arr.length; i++) {
			if (!select[i]) {
				num[cnt] = arr[i];
				select[i] = true;
				perm(cnt + 1);
				select[i] = false;
			}
		}
	}
}

 

 

---

 

중복순열

 

중복순열은 값을 중복으로 사용하기 때문에 이 값을 사용했는지 체크할 필요가 없다. 그래서 순열의 코드에서 boolean 배열로 체크하는 부분만 지워주면 중복순열의 코드이다.

 

import java.util.*;

public class Perm {
	static int n; //뽑아야 하는 수의 개수
	static int[] num; //뽑은 숫자를 저장하는 배열
	static int[] arr; //뽑을 숫자가 담긴 배열
	
	public static void main(String[] args) {
		arr = new int[5];
		
		for (int i = 0; i < 5; i++)
			arr[i] = i + 1; //1,2,3,4,5 저장
		
		n = 3;
		num = new int[3]; //5개 중 3개를 뽑아 중복순열 만들기
		
		perm(0);
	}
	
	public static void perm(int cnt) {//중복순열 코드
		if (cnt == n) {
			System.out.println(Arrays.toString(num));
			return;
		}
		
		for (int i = 0; i < arr.length; i++) {
				num[cnt] = arr[i];
				perm(cnt + 1);
		}
	}
}

 

---

 

 

 

 

조합

 

import java.util.*;

public class Comb {
	static int n; //뽑아야 하는 수의 개수
	static int[] num; //뽑은 숫자를 저장하는 배열
	static int[] arr; //뽑을 숫자가 담긴 배열
	
	public static void main(String[] args) {
		arr = new int[5];
		
		for (int i = 0; i < 5; i++)
			arr[i] = i + 1; //1,2,3,4,5 저장
		
		n = 3;
		num = new int[3]; //5개 중 3개를 뽑아 조합 만들기
		
		comb(0, 0);
	}
	
	public static void comb(int cnt, int idx) {//조합 코드
		if (cnt == n) {
			System.out.println(Arrays.toString(num));
			return;
		}
		
		for (int i = idx; i < arr.length; i++) {//idx와 i가 자주 헷갈려서 실수주의!!
				num[cnt] = arr[i];
				comb(cnt + 1, i + 1);
		}
	}
}

 

---

 

중복조합

 

사실 조합 코드에서 딱 한 줄만 달라진다. 하지만 굳이 따로 올려봄^^ 

 

import java.util.*;

public class Comb {
	static int n; //뽑아야 하는 수의 개수
	static int[] num; //뽑은 숫자를 저장하는 배열
	static int[] arr; //뽑을 숫자가 담긴 배열
	
	public static void main(String[] args) {
		arr = new int[5];
		
		for (int i = 0; i < 5; i++)
			arr[i] = i + 1; //1,2,3,4,5 저장
		
		n = 3;
		num = new int[3]; //5개 중 3개를 뽑아 중복조합 만들기
		
		comb(0, 0);
	}
	
	public static void comb(int cnt, int idx) {//중복조합 코드
		if (cnt == n) {
			System.out.println(Arrays.toString(num));
			return;
		}
		
		for (int i = idx; i < arr.length; i++) {//idx, i 구분 주의!!
				num[cnt] = arr[i];
				comb(cnt + 1, i); //i+1을 i로 바꾸고 중복으로 숫자를 선택하게 한다.
		}
	}
}

 

---

 

 

 

부분집합

 

부분집합은 위와 개념이 살짝 다르다. n개 중에 r개를 뽑는 것과 달리 n개를 뽑는데 1개 ~ 3개를 전부 뽑는 부분집합의 경우를 모두 구한다.

이때 boolean으로 부분집합의 값을 체크해서 true인 값만을 출력하면 그것이 부분집합이다.

 

public class Subset {
	static int n; //뽑아야 하는 수의 개수
	static int[] arr; //뽑을 숫자가 담긴 배열
	static boolean[] select; //index에 해당하는 숫자가 사용됐는지 저장하는 배열
	
	public static void main(String[] args) {
		arr = new int[3];
		
		for (int i = 0; i < 3; i++)
			arr[i] = i + 1; //1,2,3 저장
		
		n = 3; // 1 ~ 3개를 뽑아부분집합 만들기
		select = new boolean[5];
		
		subset(0);
	}
	
	public static void subset(int cnt) {//부분집합 코드
		if (cnt == n) {
			for (int i = 0; i < n; i++)
				if (select[i])
					System.out.print(arr[i] + " ");
			System.out.println();
			return;
		}
		
		select[cnt] = true;
		subset(cnt + 1);
		select[cnt] = false;
		subset(cnt + 1);
	}
}