알고리즘 - 부분집합과 그 합 알고리즘

SW Expert Academy 의 SW문제해결 기본 Array 2 강좌 - 2차시 주제입니다.

부분집합의 합 문제 - 모든 부분집합을 생성하는 방법

유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내야 하는 문제입니다.

• 완전 검색 기법(Exhaustive Search)를 사용한다면, 이 집합의 모든 부분집합을 생성해 놓고 각각의 합을 계산하여 0이 되는 경우를 찾을 것입니다.
• 이 모든 부분집합을 생성하는 방법은 무엇일까요?

위처럼 생각하는 아이디어를 소개했습니다. 즉, 부분집합의 경우의 수를 ‘‘비트’‘처럼 바라보면 된다는 생각입니다.

부분집합의 갯수는 2^n 입니다. (n은 원소의 갯수)

위의 예시는 집합의 원소의 갯수가 3입니다. 따라서 모든 부분집합의 갯수는 8개가 됩니다.

그리고 0 0 0 부터 1 1 1 까지 비트가 차례로 증가한다고 바라본다면, 0부터 8까지 증가한다고 볼 수 있습니다.

1인 비트일 때, 그 위치에 맞는 집합의 숫자를 출력한다면 모든 부분집합의 경우의 수를 나타낼 수 있습니다.

• 모든 부분집합의 개수 2^n를 비트 연산으로 나타내면, 1 « n 이다. (n은 원소의 갯수)
  « 는 비트 연산자로 왼쪽의 피연산자를 n번 만큼 비트를 왼쪽으로 옮기라는 의미이다.
  즉, 1 « 3은 1을 왼쪽으로 3번 밀어 binary 1000 이 되고 이는 8과 같다.

• 특정 비트가 1인지 판단하는 코드를 작성하는 아이디어는 다음과 같다.

  

부분집합을 출력하는 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <stdio.h>

int main(void){
	int i, j;
    int arr[] = {1, 3, 5, 7, 9};
    int len = sizeof(arr)/sizeof(int);
    
    for(i=0; i<(1<<n); i++){ // i는 맨 처음 그림처럼 부분집합의 최대 개수까지 하나씩 증가한다.
        printf("{")
        for(j=0; j<n; j++){
            if(i&(1<<j)){ // j가 1씩 증가할 때마다, 1을 한 칸, 두 칸, 세 칸,... 씩 밀게 된다.
                printf("%d ", arr[j]); // 그 값이 1이었을 때, j번째 원소를 출력한다.
            }
        }
        printf("}\n");
    }
}