[Algorithm] 부분집합(Subset)

개요

 

◎ 부분집합이란?

◎ 구현코드 (Java)

◎ 시간 복잡도

 

 

 

안녕하세요. J4J입니다.

 

이번 포스팅은 부분집합에 대해 적어보는 시간을 가져보려고 합니다.

 

 

부분집합이란?

 

부분집합은 고등학교 수학 시간 때 배웠던 것으로 집합 A와 집합 B가 있을 때 집합 A에 존재하는 모든 원소들이 집합 B에 존재하면 집합 A는 집합 B의 부분집합(A ⊆ B)이라고 합니다.

 

단순하게 생각하면 집합 B가 집합 A를 포함하고 있다라고도 말할 수 있습니다.

 

예를 들어 한 집합 안에 {A, B, C}라는 값이 들어있다면 이 집합의 부분집합은 다음과 같습니다.

 

1. ∅ (공집합)

2. {A}

3. {B}

4. {C}

5. {A, B}

6. {A, C}

7. {B, C}

8. {A, B, C}

 

집합의 개수가 n개가 있다고 할 때 부분집합의 개수는 2^n개만큼 나옵니다.

 

위의 예제는 n값이 3이기 때문에 부분집합의 갯수는 2^3 = 8이라는 값이 나오고 직접 구한 것과 개수가 동일하다는 것을 확인할 수 있습니다.

 

728x90

 

구현코드 (Java)

 

package math;

import java.util.ArrayList;
import java.util.List;

public class Subset {
	public static void main(String[] args) {
		String[] stringArray = new String[]{"A", "B", "C"};
		int n = stringArray.length;
		
		List<String> subsetList = new ArrayList<String>();
		
		for(int i=0; i<(1<<n); i++) {
			subsetList.clear(); // 리스트 비우기
			
			for(int j=0; j<n; j++) {
				if((i & (1<<j)) != 0) { // i의 비트를 구했을 때 j번째에 해당되는 값이 1일 경우
					subsetList.add(stringArray[j]); // j번째에 해당하는 원소값 저장
				}
			}
			
			System.out.println(subsetList); // []
								   // [A]
								   // [B]
								   // [A, B]
								   // [C]
								   // [A, C]
								   // [B, C]
								   // [A, B, C]
			}
	}
}

 

코드를 보시면 비트 연산자를 이용하여 작성된 것임을 확인할 수 있습니다.

 

코드에 대해 간단하게 설명해 보자면 n값이 3이기 때문에 첫 번째 for문의 i값은 0부터 7까지 반복을 하고 두 번째 for문은 항상 0부터 2까지 반복을 하며 if문에서 다음과 같은 결과를 만듭니다.

 

1. i=0 / j=0 ⇒ 000 & 001 = 0

2. i=0 / j=1 ⇒ 000 & 010 = 0

3. i=0 / j=2 ⇒ 000 & 100 = 0

 

4. i=1 / j=0 ⇒ 001 & 001 = 1 ⇒ j번째 값 리스트에 저장

5. i=1 / j=1 ⇒ 001 & 010 = 0

6. i=1 / j=2 ⇒ 001 & 100 = 0

 

.

.

.

 

22. i=7 / j=0 ⇒ 111 & 001 = 1 ⇒ j번째 값 리스트에 저장

23. i=7 / j=1 ⇒ 111 & 010 = 1 ⇒ j번째 값 리스트에 저장

24. i=7 / j=2 ⇒ 111 & 100 = 1 ⇒ j번째 값 리스트에 저장

 

 

시간 복잡도

 

부분집합의 시간 복잡도는 O(N x 2^N)입니다.

 

첫 번째 for문에서 2^N만큼 두 번째 for문에서 N만큼 걸리기 때문에 N x 2^N이라는 결과값을 얻을 수 있습니다.

 

 

정리

 

● 부분집합은 A집합의 원소가 B집합에 모두 포함될 때 A가 B의 부분집합이라고 함

● 시간 복잡도는 O(N x 2^N)

 

이상으로 부분집합에 대해 간단하게 알아보는 시간이었습니다.

 

읽어주셔서 감사합니다.