Computer >> 컴퓨터 >  >> 프로그래밍 >> C 프로그래밍

배열과 반복문 없이 C 프로그램으로 {1,2,3,…,n}의 모든 부분집합 출력하기

양의 정수 n이 주어졌을 때, 배열이나 반복문을 사용하지 않고 집합 {1, 2, 3, 4, …, n}의 모든 부분집합을 출력해야 합니다.

예를 들어 n = 3이 주어진다면, 집합 {1, 2, 3}의 모든 부분집합인 {1 2 3}, {1 2}, {2 3}, {1 3}, {1}, {2}, {3}, { }을 출력해야 합니다.

그런데 반복문과 배열을 사용할 수 없다는 제약 조건이 있으므로, 이러한 유형의 문제는 재귀(recursion)만이 유일한 해결 방법입니다.

예시

입력: 3
출력: { 1 2 3 }{ 1 2 }{ 1 3 }{ 1 }{ 2 3 }{ 2 }{ 3 }{ }
설명: 집합 {1 2 3}으로부터 모든 부분집합을 찾아 출력합니다.

입력: 4
출력: { 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }

문제 해결 접근 방식

  • num = 2^n − 1부터 시작하여 0까지 진행합니다.
  • num을 n비트 크기의 이진수로 표현합니다.
  • 가장 왼쪽 비트는 1을, 두 번째 비트는 2를 나타내며, 이런 식으로 n번째 비트는 n에 대응됩니다.
  • 비트가 설정되어 있다면(set) 그 비트에 해당하는 숫자를 출력합니다.
  • num이 0이 될 때까지 위 과정을 반복하여 모든 부분집합을 출력합니다.

동작 원리 상세 분석

간단한 예제를 통해 이 접근 방식이 실제로 어떻게 동작하는지 살펴보겠습니다.

입력 n = 3이라고 가정하면, num = 2^3 − 1 = 7부터 시작합니다.

  • 7의 이진수 표현 ⇒
111
  • 대응되는 부분집합 ⇒
123

num에서 1을 빼면 num = 6

  • 6의 이진수 표현 ⇒
110
  • 대응되는 부분집합 ⇒
12

num에서 1을 빼면 num = 5

  • 5의 이진수 표현 ⇒
101
  • 대응되는 부분집합 ⇒
1
3

num에서 1을 빼면 num = 4

  • 4의 이진수 표현 ⇒
100
  • 대응되는 부분집합 ⇒
1

이와 같은 방식으로 num = 0이 될 때까지 반복하면서 모든 부분집합을 출력하게 됩니다. 즉, 각 숫자의 이진수 표현에서 켜져 있는(on) 비트 위치가 곧 해당 부분집합에 포함되는 원소를 의미합니다.

알고리즘

시작
    단계 1 → 함수 int subset(int bitn, int num, int num_of_bits)
    If bitn >= 0
        If (num & (1 << bitn)) != 0
            num_of_bits - bitn 값 출력
            subset(bitn - 1, num, num_of_bits) 호출
        Else
            Return 0
        Return 1
    단계 2 → 함수 int printSubSets(int num_of_bits, int num)
        If (num >= 0)
            "{ " 출력
            subset(num_of_bits - 1, num, num_of_bits) 호출
            "}" 출력
            printSubSets(num_of_bits, num - 1) 호출
        Else
            Return 0
        Return 1
    단계 3 → 함수 int main()
        int n = 4 선언 및 초기화
        printSubSets(n, (int)(pow(2, n)) - 1) 호출
종료

C 코드 구현

#include <stdio.h>
#include <math.h>
// 이 함수는 num의 이진수 표현에 대응하는
// 부분집합을 재귀적으로 출력합니다.
int subset(int bitn, int num, int num_of_bits) {
    if (bitn >= 0) {
        // num에서 해당 비트가 설정되어 있는 경우에만
        // 그 비트에 대응하는 숫자를 출력합니다.
        if ((num & (1 << bitn)) != 0) {
            printf("%d ", num_of_bits - bitn);
        }
        // 다음 비트 검사
        subset(bitn - 1, num, num_of_bits);
    }
    else
        return 0;
    return 1;
}
// 부분집합을 출력하는 함수
int printSubSets(int num_of_bits, int num) {
    if (num >= 0) {
        printf("{ ");
        // num의 이진수 표현에 대응하는
        // 부분집합을 출력합니다.
        subset(num_of_bits - 1, num, num_of_bits);
        printf("}");
        // 다음 부분집합을 출력하기 위해
        // 함수를 재귀적으로 호출합니다.
        printSubSets(num_of_bits, num - 1);
    }
    else
        return 0;
    return 1;
}
// 메인 프로그램
int main() {
    int n = 4;
    printSubSets(n, (int) (pow(2, n)) -1);
}

실행 결과

{ 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }

복잡도 분석

n개의 원소를 가진 집합의 부분집합 개수는 총 2^n개이며, 각 부분집합을 출력하는 데 최대 n번의 비트 검사가 필요하므로 시간 복잡도는 O(n × 2^n)입니다. 공간 복잡도는 추가적인 배열을 사용하지 않고 재귀 호출 스택만 활용하므로 O(n)입니다.