[Algorithm] 멱집합(powerSet)알고리즘

정말 무식하게 0부터 1씩 증가시키면서 무식하게 이 수가 감소하는 수 인지를 매 번 while문으로 체크를 하다가 이건 도저히 아닌 것 같아서

고수님의 풀이를 보았다. 가장 신박하면서도 수학적인 원리로 이 문제를 접근하셨는데. 10진수로 만들 수 있는 감소하는 수는 1023개밖에 되지 않는 다는 사실로부터 출발하는 것이었다.

 

왜 감소하는 수는 1023개밖에 존재하지 않는 걸까?

우리는 중등수학(고등학교)의 집합단원을 공부하면서 n개의 원소로 만들 수 있는 부분집합의 개수는 총 2^n개라는 것을 배운 적이 있다.

예를 들어 1과 2로 만들 수 있는 부분집합은

{ Ø : 공집합 }

{ 1 }

{ 2 }

{ 1 , 2 }

로 총 4가지가 있고 2^(2개) = 4와 일치한다는 것을 알 수 있다.

공식은 저렇게 되어 있지만, 좋은 고등학교를 나온 사람들은

{ 1, 2 } 라는 집합으로 만들 수 있는 부분집합들을 구하기 위해서

x라는 특정원소를 포함하는 경우와 포함하지 않는 경우로 나누어서 생각하는 아이디어를 배운 사람이 있을 것이다.

 

멱집합을 구하기 위해서는 x라는 원소를 집합에서 제외한 경우의 케이스를 구한 다음,

거기에 x를 포함시킨 경우를 모두 더해주면 된다.

 

재귀적으로 생각해보자면,

{1, 2 }가 있을 때,

1을 선택하지 않고 만든 경우의 수는

{ 공집합 } , { 2 } 가 있는데.

위에서 말한대로 여기에 1을 선택한 경우를 넣어보자

{ 1 } , { 1, 2} 가 나온다.

이 모든 것을 다합친

{공집합} , { 2 } , { 1 } , { 1, 2 } 를 보면 역시나 위에서 구한 것과 똑같다.

이처럼  컴퓨터에게도 x를 선택한 경우와 선택하지 않은 경우로 분기시켜서 명령을 내려주면 멱집합을 구해준다.

이를 소스코드로 나타내면 다음과 같다.

1 2 3 4

chk[k] = false; powerSet(arr, chk, n, k+1); chk[k] = true; powerSet(arr, chk, n, k+1);

arr: 원소들이 담긴 배열

chk : 선택 했는지 안 했는지를 체크하는 arr사이즈 만큼의 boolean 배열

n: 재귀가 끝나는 시점

k: arr 배열 안에서 현재 선택하고자 하는 원소의 인덱스

 

를 의미한다.

아래는 멱집합의 소스코드이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

public class PowerSet {     private static void powerSet(int[] arr, boolean[] chk, int n, int k)     {         if (k == n)         {             StringBuilder sb = new StringBuilder();             sb.append("{");             for (int i = 0; i < n; i++)             {                 if (chk[i])                 {                     sb.append(arr[i]+" ");                 }             }             sb.append("}");             System.out.println(sb);               return;         }         chk[k] = false;         powerSet(arr, chk, n, k+1);         chk[k] = true;         powerSet(arr, chk, n, k+1);     }       public static void main(String[] args)     {         System.out.println("멱집합을 출력해봅시다.");           int[] arr = {0, 1, 2};         powerSet(arr, new boolean[arr.length], arr.length, 0);     }

 

처음에는 굉장히 낯설지만, 상태공간 트리를 한 3번 정도 그려보면, 그 때서야 감이 오기 시작한다!

그리고 관련 된 문제를 풀다보면, 외우기 싫어도 코드가 외워지게 되고, 어느 순간 서당개처럼 이해하는 순간이 온다.

이 연습을 하고나면 재귀함수를 추상적으로 생각할 수 있는 힘이 길러지게 된다.

꼭꼭 익히도록 하자!