부분집합_재귀함수_멱집합 구하기 (JAVA)

[ 멱집합(powerset) ]

• 공집합을 포함해 모든 부분집합을 가진 집합 (중복 없음)
  

어떠한 집합의 부분집합을 산출하는 로직은 여러 가지가 있습니다. 그 중 모든 부분집합(멱집합)을 가장 쉽게 구할 수 있는 재귀함수 사용법입니다. 원소 순서에 상관없이 중복을 허용하지 않기 때문에 rCr의 조합과 동일한 결과입니다. 

 

---

 

아래 3개짜리 배열이 하나 있다고 해보겠습니다.

 

* 집합 : { a, b, c }

 

 

먼저 가장 앞에 있는 "a"의 기준에서 생각해봅니다. "a"는 부분집합에 있을 수도 있고 없을 수도 있습니다. 따라서 "a"가 있건 없건 부분집합을 구하기 위해서는 { b, c }의 부분집합 정보가 필요합니다. 피보나치 수열과 같이 큰 문제를 해결하기 위해 작은 정보가 필요한 경우입니다.

 

 

 

그럼 이번엔 { b, c }의 부분집합을 봅니다. 역시 마찬가지로 "b"는 자신이 있건 없건 { c }의 부분집합이 필요합니다. 따라서 최종적으로 { c }의 부분집합을 가장 먼저 구해야합니다.

 

{ c } 는 요소가 딱 한 개 남았기 때문에 다른 집합의 정보 없이 자신의 부분집합을 구할 수 있습니다. { c }, { } 2개의 상태 즉, "내가 있거나 없거나" 라는 의미입니다. 

 

따라서 이제 재귀함수의 끝이 정해졌습니다. 배열의 인덱스가 가장 마지막에 도달했을 경우 부분집합을 구한 뒤 리턴을 시켜 탈출해줍니다. 일단 아래와 같이 작성합니다. 

 

package pojoPrj;

public class Solution {

	public static void main(String[] args) {

		// 원본 집합
		String[] arr = new String[] { "a", "b", "c" };
	}

	/**
	 * 모든 부분집합 구하기
	 * 
	 * @param arr   : 원본 배열
	 * @param index : 현재 기준이 되는 인덱스
	 * @param end   : 배열의 사이즈
	 */
	public static void powerset(String[] arr, int i, int end) {

		// 탈출문
		if(i >= end) {
			
			// 부분집합 구하는 로직
			
			return;
		}
	}
}

 

 

---

 

 

골치가 아픈 부분은 탈출문 안에서 부분집합을 구하는 로직입니다. 가장 직관적으로는 마지막의 "c"가 자신의 부분집합인 { c }, { } 두 배열을 리턴해주면 "b"가 두 배열에 자신이 있을 경우를 추가해서 "{ c }, { } + { b, c } { b }" 4개의 배열을 만들어 리턴해주는 것입니다.

 

그리고 "a"는 다시 이걸 받아서 동일하게 4개의 배열에 "a"가 있을 경우를 추가해 최종적으로 8개의 부분집합으로 이루어진 멱집합을 만들어냅니다. 멱집합의 갯수를 구하는 점화식 2^n이 만들어지는 과정입니다.

 

 

 

아마 똑똑한 사람들이 알고리즘을 만들어두지 않았으면 저는 위와 같은 로직으로 코드를 짰을 것 같습니다. 

 

 

 

---

 

 

원리는 위와 같지만 약간의 로직을 추가해 훨씬 간결하고 편하게 코드를 작성할 수 있습니다. 추가된 로직의 핵심은 "내가 있거나 없거나" 입니다. 이를 위해 "있는 상태"와 "없는 상태"를 체크해주기 위한 boolean 타입의 배열을 추가해준 뒤 아래와 같이 재귀함수를 호출해 코드를 작성합니다. 공집합 포함 8개의 부분집합이 잘 출력되는 것을 확인할 수 있습니다.

 

package pojoPrj;

public class Solution {

	public static void main(String[] args) {

		// 원본 집합
		String[] arr = new String[] { "a", "b", "c" };

		// 상태 체크
		boolean[] state = new boolean[arr.length];

		// 멱집합 재귀함수 호출
		powerset(arr, state, 0, arr.length);
	}

	/**
	 * 모든 부분집합 구하기
	 * 
	 * @param arr   : 원본 배열
	 * @param state : "있을 경우와 없을 경우" 상태값 체크
	 * @param index : 현재 기준이 되는 배열 인덱스
	 * @param end   : 배열의 사이즈
	 */
	public static void powerset(String[] arr, boolean[] state, int i, int end) {

		// 탈출문
		if (i >= end) {

			// 현재 true로 체크되어 있는 인덱스의 값만 출력
			for (int w = 0; w < end; w++) {

				if (state[w]) {
					System.out.print(arr[w] + " ");
				}
			}
			System.out.println();

			return;
		}

		// "내가 없을 경우"를 체크한 뒤 다른 부분집합을 구하는 재귀함수 호출 (다음 인덱스로 기준 이동)
		state[i] = false;
		powerset(arr, state, i + 1, end);

		// "내가 있을 경우"를 체크한 뒤 다른 부분집합을 구하는 재귀함수 호출 (다음 인덱스로 기준 이동)
		state[i] = true;
		powerset(arr, state, i + 1, end);
	}
}

 

 

---

 

 

간단히 생각하면 아래와 같은 원리입니다.

 

일단 재귀함수가 처음 호출되면 탈출조건에 도달하기 전까지 "내가 없을 경우"를 수행합니다. 계속 첫 번째 재귀함수를 호출해 탈출조건까지 들어가는 거죠. 탈출 조건이 배열의 사이즈(인덱스 + 1)에 도달했을 때이니, 바로 전 단계를 보겠습니다. 

 

탈출조건에 걸리기 바로 전 단계를 위에서 설명한 { c } 값만 남았을 때입니다. 이제 "c"는 본인이 있거나 없거나를 결정해야할 때입니다. 먼저 현재 "c"의 상태값을 false로 줬으므로 "없거나" 상태입니다. 그 상태로 다시 재귀함수를 한번 더 호출해서 탈출 구문에 들어갑니다. 3개의 값 모두 "내가 없거나" 상태이므로 부분집합 중 공집합을 출력합니다. 

 

 

 

탈출문에서 재귀함수가 리턴됐으므로 이번엔 "내가 있거나"로 상태를 바꿔줍니다. 그리고 재귀함수를 호출하게 되면 이번엔 { c } 하나가 들어간 부분집합을 출력하게 되는 것이죠.

 

 

---

 

 

위 재귀함수는 { b }가 "내가 없거나" 상태로 호출 당해 수행된 것입니다. 따라서 모두 수행 후 리턴되면 이제 { b }는 다시 "내가 있거나" 상태로 재귀함수를 호출해 { c }에게 부분집합을 달라고 합니다. 이 때 b의 상태값은 true가 되었으므로 아래와 같이 수행됩니다.

 

 

 

---

 

 

쉽게 생각하면 재귀함수에 들어가서 빠져나올 때까지의 상태값 고정해서 내가 있을 경우와 없을 경우를 구분해준다고 보면 됩니다. 멱집합을 구할 때 간단히 사용할 수 있지만 사실 부분집합 중 조합을 구하는 방법을 사용해도 동일하기 때문에 이 방법보다는 조합과 순열 코드를 잘 알아두는 것이 더 좋을 듯합니다. 다음 글에서 다루도록 하겠습니다.