멱집합

Recursion으로 먹집합을 구성해보겠습니다.

멱집합이란? 모든 부분 집합을 모은 집합을 의미합니다.

멱집합 A가 존재한다고 할 때 A을 나타내는 기호는 P(A) 나 이다. 예를 들어, { A={1,2}} A = {1, 2} 의 멱집합은 P(A) = {공집합, {1}, {2}, {1,2}} 이다.

멱집합의 특징을 고려해서 다음과 같이 규칙을 만들 수 있습니다.

규칙 1. 부분집함을 구성 시 부분집합의 각 요소는 포함 하는 경우와 포함하지 않는 경우로 나눈다.

규칙 2. 공집합도 집합으로 구분되며, P(A)는 2^A이다.

규칙 1을 그래프로 표시하면 다음과 같이 표시할 수 있습니다.

가장 상단부터 해서 왼쪽은 포함되지 않는 것, 오른쪽은 포함된 것으로나눠서 표시한 그래프입니다.

각 원소의 포함 여부를 저장하는 boolean[] 을 구성합니다.

boolean[] hasThis;

그래프 구성은 가장 위에는 공집합을 의미하며 위에서부터 하나씩 각 원소로 생각하면 이해하기 쉬울 것입니다.

위에서 아래로 내려가면서 나눠지는데 왼쪽은 포함하지 않은, 오른쪽은 포함을 표시합니다.

이것을 소스로 표현 하면 현재 포함 여부를 boolean 값으로 표시 후 다음 행 실행으로 진행합니다.

hasThis[position] = true;
checkUp(position + 1);
​
hasThis[position] = false;
checkUp(position + 1);

가장 하단(각 원소들의 끝에 행)으로 왔을 시 포함된 부분의 원소만 보여주면 멱집합을 그릴 수 있습니다.

멱집합 구하는 전체 소스를 살펴보겠습니다.

Day001.java

public class Day001 {
    static boolean[] hasThis;
    static char[] datas = new char[] {'a', 'b', 'c', 'd','e'};
    // 먹집합 알고리즘
    // 먹집합 알고리즘은 2^n을 값을 갖고있다. 
    // 자신을 포함하는 경우와 포함하지 않는 경우로 나눠진다.
    private static void checkUp(int position) {
        if (position == hasThis.length - 1) {
            System.out.print("{");
            int pos = 0;
            for (boolean hThis : hasThis) {
                if (hThis) {
                    System.out.print(datas[pos]);
                }
                pos++;
            }
            System.out.print("}");
            return;
        }
        
        hasThis[position] = true;
        checkUp(position + 1);
        
        hasThis[position] = false;
        checkUp(position + 1);
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        hasThis = new boolean[3];
        checkUp(0);
    }
}

마무리

멱집합에 대해서 개념을 알고 있으니 풀이까지 해보는 것은 처음이었습니다.

멱집합 같은 포함, 불포함에 따른 그래프 표시가 가능한 문제 같은 경우는 boolean[]을 만들어 접근하면 보다 쉽게 문제를 해결할 수 있습니다.