DP 이용 부분 집합(power set with DP)

다른 글에서 부분 집합을 재귀와 binary counting을 이용하여 구하는 것을 살펴 보았습니다.
부분 집합이란? 그리고 재귀를 이용한 부분집합
여기에서는 DP를 이용하여 어떻게 구현하면 되는지에 대한 설명입니다.

앞에서 부분 집합을 만들때 선택하고 안하고를 하게 되어 피라미드 형태를 가지게 됨을 알수 있습니다.

위와 같은 식으로 생각해볼 수 있습니다. 추가되는 item은 이전 단계의 결과를 그대로 가져오는것과 가져온 데이터각각에 현재 item을 추가하여 2^N승 개의 경우의 수가 생겨납니다.
DP로 구현하게되면 depth별로 계산하여 한꺼번에 내려가기 때문에 많은 메모리가 필요합니다.
기본적으로는 depth별로 집합이 몇개 있는지와 집합안에 원소가 몇개 있는지 배열이 있어야 합니다. 즉 result[Depth][2^N][N]; 의 3차원 배열이 필요하게 됩니다.

아래 C 샘플 코드가 있지만 아래는 샘플을 위한것이고 위점화식에서는 최종 단계를 위해서는 항상 그 이전 단계의 데이터만 있으면 되므로 이론적으로는 이런식으로, result[2][2^N][N]; 2개의 depth를 가지고 있으면 됩니다.

C, pasted just now:  #include <stdio.h> #define MAX_N 10 #define MAX_DEPTH MAX_N #define MAX_POW_2_N 1024 int data[]={10,20,30}; int N = 3; int result[MAX_DEPTH][MAX_POW_2_N][MAX_N]; int count[MAX_DEPTH][MAX_POW_2_N]; int countItem[MAX_DEPTH]; int main() { int depth,itemi,addi,i,sets; int cur_item; for(depth=0;depth<=N;depth++){ if(depth==0){ continue; } cur_item = data[depth-1]; addi = countItem[depth-1]; for(itemi=0;itemi<countItem[depth-1];itemi++){ for(sets=0;sets<count[depth-1][itemi];sets++){ result[depth][itemi][sets] = result[depth-1][itemi][sets]; } count[depth][itemi] = count[depth-1][itemi]; } countItem[depth] += addi; for(itemi=0;itemi<countItem[depth-1];itemi++){ for(sets=0;sets<count[depth-1][itemi];sets++){ result[depth][itemi+addi][sets] = result[depth-1][itemi][sets]; } result[depth][itemi+addi][sets]=cur_item; count[depth][itemi+addi] = count[depth-1][itemi] + 1; } countItem[depth] += addi; result[depth][countItem[depth]][0]=cur_item; count[depth][countItem[depth]]=1; countItem[depth]++; } // print for(depth=0;depth<=N;depth++){ printf("[depth:%d]:",depth); for(itemi=0;itemi<countItem[depth];itemi++){ for(sets=0;sets<count[depth][itemi];sets++){ printf("[%d]",result[depth][itemi][sets]); } printf("/"); } printf("\n"); } return 0; } Output: [depth:0]: [depth:1]:[10]/ [depth:2]:[10]/[10][20]/[20]/ [depth:3]:[10]/[10][20]/[20]/[10][30]/[10][20][30]/[20][30]/[30]/