티스토리 뷰

# 멱집합 구하는 문제


 문제) S가 n개의 원소로 된 집합일 때 S의 멱집합(powerset)모든 가능한 S의 부분집합이다. 즉, S = { a, b, c }이면 powerset(S) = { { }, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c } } 이다. powerset(S)를 구하는 순환 함수를 작성하라.



# 풀이


 비트 연산을 이용하는 문제다. 순환으로 구현해야 하는 만큼 순환별 규칙을 생각할 필요가 있었고, 값을 하나 증가시키는 걸 그 규칙으로 삼았다. 하나의 순환 안에서의 반복문이 비트연산의 핵심인데, 처음엔 이해가 어려워도 하나하나 손으로 써가면서 확인하면 그 규칙이 눈에 들어올 것이다.

/************************************************* ** MAT program comments *************************************************/ #include <stdio.h> #include <math.h> // pow()사용을 위함 #define MAX 3 // n개의 원소 char S[MAX] = { 'a', 'b', 'c' }; void powerset(char bit); void main() { // bit연산을 위한 변수, char = 8bit, 만약 더 큰 집합이 있다면 int 나 long int로 변경하면 된다. char bit = 1; printf("Powerset(S) = {"); powerset(bit); printf("}\n"); } // 001->a, 010->b, 100->c ... 000->공집합 void powerset(char bit) { int i; printf("{"); for (i = 0; i < MAX; i++) // 각 순환별 MAX번 반복한다. { // bit 연산 // 1을 왼쪽으로 i번 쉬프트 한다. if (bit & (1 << i)) { // 1 << i는 각 실행별 001, 010, 100으로 된다. printf("%c ", S[i]); } } printf("}, "); /* bit값이 2의 3승, 즉 8이 될 때까지 recursion */ bit++; if (bit == pow(2, MAX)) // bit가 2의 MAX승이 되면 { /* 공집합 생성 */ printf("{ }"); return; } // 값이 1증가한 bit를 다시 매개변수로 넘겨준다. powerset(bit); } /************************************************* ** End Line *************************************************/


댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday