문제로 풀어보는 알고리즘 149쪽 문제 3.c 풀이

첫 문제에 이어 두 번째 문제에 도전했다. (책표지 서비스~ 부탁받은대로~ㅋㅋ)

아래 책에 있는 문제라네.

두번째 문제는 개인적으로 너무 어려웠다. 아.. 남은 문제들은 어떻게 푸냐 -_-;;;

규칙을 찾는데 상당히 오래 걸렸는데 그 규칙은 다음과 같다.

1. 이전에 만들어진 집합에 현재 값을 포함시켜 새로운 집합으로 만든다. {} 쌍으로 된 것을 하나의 집합이라 한다.

2. 이전 집합과 별도로 독립적인 집합을 만든다. 그리고 그 결과를 취합한다.

ex) {0}에 {1}을 넣어야 하는 경우

기존 집합에 넣기: {0, 1}

독립적 집합 만들어 합치기: {0}, {1}

위에다 {2}를 넣으면?

기존 집합에 넣기: {0, 1, 2}, {0, 2}, {1, 2}

독립적 집합 만들어 합치기: {0, 1}{2}, {0}{1}{2}

...

이렇게 되는 것이다. 이걸 찾아내는게...참.. 후덜덜..ㅠㅠ

Python, C++, Perl 등 고차원 언어로 짜면 더 간단하게 표현 할 수 있겠지만 난 C로 짰다.

C로 구현하려니 독립적인 집합 표현하기가 힘들었다.

구조체를 이용하다가 코드가 지저분해져서 array의 index를 집합에 들어갈 값으로 하고, 

array 값을 집합 번호로 만들어 구현했다. 덕분에 코드는 좀 깔끔하게 나온듯하다.

#include <stdio.h>

//================================================
// TEST SET
//================================================
const int MAX_N = 16;
const int N = 4;
//================================================

int getMaxGroup(int *array, int size)
{
	int maxGroup = -1;

	for(int i = 0; i < size; i++) {
		if (array[i] > maxGroup) 
			maxGroup = array[i];
	}

	return maxGroup;
}

void printArray(int *array, int size)
{
	int maxGroup = getMaxGroup(array, size);

	for(int i = 0; i <= maxGroup; i++) 
	{
		printf("{");
		for(int j = 0; j < size; j++) {
			if (array[j] == i) {
				printf(" %d ", j);
			}
		}
		printf("}");
	}
	printf("\n");
}

void makeset(int *array, int size, int depth)
{
	if (depth == N) {
		printArray(array, size);
		return ;
	}

	// make new group 
	int maxGroup = getMaxGroup(array, size);

	array[depth] = maxGroup+1;
	makeset(array, size, depth+1);
	array[depth] = -1;

	// attach new element to each group
	for(int i = 0; i <= maxGroup; i++) {
		array[depth] = i;
		makeset(array, size, depth+1);
		array[depth] = -1;
	}
}

int main()
{
	int array[MAX_N];

	// init
	for(int i = 0; i < N; i++) {
		array[i] = -1;
	}

	makeset(array, N, 0);
	return 0;
}

어쨌든 풀어서 기분이 좋군 :)

실행결과

{ 0 }{ 1 }{ 2 }{ 3 }

{ 0  3 }{ 1 }{ 2 }

{ 0 }{ 1  3 }{ 2 }

{ 0 }{ 1 }{ 2  3 }

{ 0  2 }{ 1 }{ 3 }

{ 0  2  3 }{ 1 }

{ 0  2 }{ 1  3 }

{ 0 }{ 1  2 }{ 3 }

{ 0  3 }{ 1  2 }

{ 0 }{ 1  2  3 }

{ 0  1 }{ 2 }{ 3 }

{ 0  1  3 }{ 2 }

{ 0  1 }{ 2  3 }

{ 0  1  2 }{ 3 }

{ 0  1  2  3 }