부분집합(Powerset)에 대하여.java

 

안녕하세요

오늘은 부분집합에 대한 간단한 설명 및 구현 코드를 통해

코드로 수학시간에 배웠던 부분집합을 새롭게 느껴보려고 합니다.

 

---

부분집합 (Powerset)

학창시절 수학의 정석을 펼치면 늘 1단원에 있던, 집합

저희는 모두 1단원 반복문에 갇혀 나오지 못한 경험이 있으니 집합에 대해서 다들 알고 계시겠죠?

 

부분집합은, literally 어떤 집합의 부분들에 대한 집합입니다.

 

나만의 라면 레시피를 만든다고 가정해보겠습니다.

들어갈 수 있는 재료는 다음과 같습니다.

 

{치즈, 계란, 대파, 새우, 홍합}

 

이제 이 재료들의 부분집합을 계산한다면,

각 재료들에 대해 들어가는 경우와 들어가지 않는 경우를 나누어

 

 2*2*2*2*2 = 32

 

그럼 이제 32가지의 집합들을 출력하는 코드를 구현해보겠습니다.

---

반복문을 활용한 구현 💻

public class 부분집합by반복문 {
	public static void main(String[] args) {
		String[] 라면재료 = { "치즈", "계란", "새우","홍합"};
		int ingredient = 4; // 재료는 4개
		int[] selected = new int[ingredient];
		//배열 값이 0 : 재료 안들어간다, 1: 재료 들어간다.
		for (int i = 0; i < 2; i++) {
			selected[0] = i;
			for (int j = 0; j < 2; j++) {
				selected[1] = j;
				for (int k = 0; k < 2; k++) {
					selected[2] = k;
					for (int l = 0; l < 2; l++) {
						selected[3] = l;
						for (int m = 0; m < ingredient; m++) {
							if (selected[m] == 1) //재료 들어가 있으면
									System.out.print(라면재료[m]);
						}
							System.out.println("라면");
					}
				}
			}
		}
	}
}

 

보기에 어떠신가요?

시간복잡도 측면에서 5중 for문은 원소가 많아질수록, 그 시간이 기하급수적으로 증가한다는 점을 고려했을 때

상당히 비효율적이겠다, ( O(2^5)) 느끼실 겁니다.

 

---

비트마스크를 활용한 구현 💻

비트연산자 &, |는  보통 단축평가를 하고 싶지 않을 때 많이 사용하시는데요.

비트연산자를 일종의 1차원 배열의 boolean 형태로 관점을 혼합하여 사용한다면,

 

간단히 부분집합을 구할 수 있습니다😀

public class 부분집합by비트마스크 {
	public static void main(String[] args) {
		String[] 라면재료 = { "치즈","계란","새우","홍합" };
		int ingredient = 4; // 재료는 4개
		
		// 4개의 재료를 이용하여 만들 수 있는 모든 경우의 수
		for (int i = 0; i < (1 << ingredient); i++) {
			// 재료의 갯수만큼 비트연산 << 해주기 재료의 부분집합의 수만큼 반복
			String tmp = "";
			for (int j = 0; j < ingredient; j++) { // 재료 검사!
				// 1이라고 하는 값을 j번 << 하면서 값을 비교한다.
                // 각자리의 수가 1인지, 0인지를 &를 사용하여 비교한다면??! 
				if ((i & (1 << j)) > 0) { //각 이진자리의 위치별 가지고 있는 값만 반환가능!
					tmp += 라면재료[j]; 
				}
			}
			System.out.println(tmp);
		}
	}
}

 

 

재귀를 활용한 구현 💻

마지막으로 재귀를 활용한 부분집합의 구현을 보겠습니다.

public class 부분집합by재귀함수 {
	static String[] 라면재료 = { "치즈","계란","새우","홍합" };
	static int ingredient; // 재료 개수
	static boolean[] selected; // 재료의 사용유무

	public static void main(String[] args) {
		ingredient = 4;
		selected = new boolean[ingredient]; //판별해줄 boolean 정의하기

		powerset(0);
	}

	// idx : 해당 재료의 인덱스
	public static void powerset(int idx) {
		// 기저조건 : 재귀를 빠져나갈 조건
		if (idx >= ingredient) { //idx가 ingredint 이상이라면?!, 재료 다 본거지 ? 이제 빠져나갈거야
			String tmp = "";
			for (int i = 0; i < ingredient; i++) {
				if (selected[i])
					tmp += 라면재료[i];
			}
			System.out.println(tmp);
			return;
		}
		// 재귀조건 : 함수를 호출하는 부분
		selected[idx] = true;// idx 원소 재료 넣을거야
		powerset(idx + 1); // 다음 재료는 ??

		selected[idx] = false; // idx 재료 넣었던 거 이제 뺄게!
		powerset(idx + 1); // 다음 재료는 ??

		// return ; 사실 return이 생략되어 있는거야!
	}
}

 

읽어주셔서 감사합니다.😁