집합의 부분 집합 출력하기 - 상태공간트리

1. 문제

입력으로 ABC가 입력되었다고 가정했을 때,

이 ABC의 부분집합들을 출력하면 된다.

 

입력

ABC

 

출력

{ }

{ A }, { A, B }, { A, B, C }

{ B }, { B, C }

{ C }

 

구현방법

먼저, 출력의 형태를 다음과 같이 다시 써보도록 하자.

집합의 원소 개수가 3일 때, 부분집합의 개수는 총 2^3 = 8개가 나온다.

구현 방식은 두 가지가 있다.

첫 번째 방식은 별도의 출력 배열을 가지고 있는 경우와

두 번째 방식은 별도의 메모 배열( 동적 프로그래밍을 위한 )을 두고서 기록하는 경우이다.

두 부분에서 일치하는 방식은 아래와 같다.

먼저 사용자로부터 집합 원소의 개수를 입력 받도록 하자.

입력으로 3이 들어오면, 3칸짜리 char형 배열이 만들어지면서 이 배열안에 각 각 'A', 'B', 'C'가 저장이 되도록 하자.

여기까지가 첫 번째 방법과 두 번째 방법의 공통된 부분이다.

 

아래의 그림을 보도록 하자.

임의의 집합의 모든 부분 집합의 개수는 2^n개이다.  
2^n인 이유는 각 원소가 부분집합에 포함될 때와 포함되지 않을 때 두 가지 경우의 수를 가지기 때문이다. 

그리고 원소의 개수가 n개이기 때문에 2^n이 된다. 이 원리를 이용해서 만든 트리가 아래의 트리이다. 

각 레벨마다 원소가 포함되는지 안 되는지의 경우로 나누면 된다. 

아래 그림은 우리가 구현할 내용의 재귀함수의 호출 스택과 같다.

주황색 숫자가 재귀함수의 호출 스택 순서이다.

이는 곧 이진 트리와 형태가 같음을 알 수 있다.

Level은 이 이진트리에 트리의 높이로 보도록 하자.

위의 이진 트리는 레벨 0부터 마지막 레벨 순으로 탐색한다. 

현재 마지막 레벨을 탐색했다면 이는 모든 원소에 대해서 부분집합에 포함시킬 지의 여부를 결정한 것이다. 

위의 조건이 맞지 않다면 현재 탐색 중인 레벨에 대해 원소를 포함할지 혹은 제외할지 결정해야 한다. 
원소를 제외한다면, 다음 레벨로 바로 이동하면 된다.

원소를 포함한다면, 저장하는 배열에 포함시킬 원소를 집어넣어야 한다. 

 

2 - (1). 구현

첫 번째 방법에서는 출력 배열이 필요하다.

출력 배열 또한 배열의 길이가 입력 배열과 같다.

그 이유는 위의 표현법에서 입력배열의 원소 개수가 3개이면 부분배열에는

가장 많이 부분집합에 속하는 원소는 3개이다. ( { A, B, C } )

우리가 입력으로 받은 집합 배열을 출력 배열에 하나의 부분 배열을 완성시키면 그 때의 출력 배열을 출력하면 된다.

프로그램 실행결과

소스 파일

main.c

0.00MB

 

2 - (2). 구현

 

프로그램 실행결과

소스 파일

main.c

0.00MB

 

2 - (3). 구현

프로그램 실행결과

소스 파일

main.c

0.00MB

 

 

아래의 구현 방식은 위의 구현 방식과 다르게 아래와 같이 출력이 되도록 만든 것이다.

아래의 그림은 위의 그림과는 반대인 것을 알 수 있다.

 

2 - (4). 구현

2 - (1)을 반대로 만들면 된다.

프로그램 실행결과

소스 파일

main.c

0.00MB

 

 

2 - (5). 구현

2 - (2)를 반대로 만들면 된다.

프로그램 실행결과

소스 파일

main.c

0.00MB

 

2 - (6). 구현

2 - (3)을 반대로 만들면 된다.

프로그램 실행결과

소스 파일

main.c

0.00MB