[알고리즘] 부분집합(Subset)

부분집합(Subset)이란?

부분집합은 주어진 집합의 원소들 중 일부를 선택하여 형성된 집합을 말한다. 주어진 집합 S의 모든 가능한 부분집합을 구하는 것이 부분집합 문제이다. 예를 들어, 집합 S = {A, B, C}의 부분집합은 0(공집합), {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C}와 같다.

쉽게 말해 순서가 바뀌어도 연산(혹은 값)이 동일하고 선택해야 하는 개수가 따로 고정되어 있지 않은 모든 경우라면 부분집합을 고려해 볼 수 있겠다.

 

 

시간 복잡도

부분집합을 생성하는 시간 복잡도는 O(2^N)이다. 이는 각 원소에 대해 두 가지 선택(포함 또는 미포함)이 가능하므로, 모든 가능한 부분집합을 생성하기 위해 2^N개의 경우를 탐색해야 함을 의미한다. 이로 인해 입력 값 N이 증가할수록 연산량이 급격히 증가한다.

 

 

재귀 호출을 활용한 부분집합 생성

재귀 호출(Recursive Call)은 함수가 자기 자신을 호출하여 문제를 해결하는 방법이다. 부분집합 생성에서 재귀 호출은 문제를 하위 문제로 나누어 해결하는 데 매우 유용하다. 재귀를 사용하면 복잡한 부분집합 생성 문제를 더 간단하게 해결할 수 있다.

재귀를 사용한 부분집합 생성의 기본 원리는 다음과 같다.

1. 기본 상태 확인 : 모든 원소에 대해 선택 여부를 결정한 경우, 현재 상태를 출력하거나 저장한다.
2. 재귀 호출 : 각 원소에 대해 두 가지 경우를 재귀적으로 고려한다. 원소를 선택한 경우와 선택하지 않은 경우 모두 재귀 호출을 통해 처리한다.

 

코드를 통한 이해

import java.util.Arrays;

public class Subset {
    static int N = 3; // 원소의 개수
    static String[] cards = {"A", "B", "C"}; // 원소
    static boolean[] select = new boolean[N]; // 각 원소의 선택 여부

    public static void main(String[] args) {
        subset(0); // 부분집합 생성 시작
    }

    static void subset(int idx) {
        if (idx == N) { // 기본 상태: 모든 원소에 대해 선택 여부 결정
            System.out.println(Arrays.toString(select)); // 현재 선택된 원소를 출력
            return;
        }

        select[idx] = true; // 현재 원소를 선택
        subset(idx + 1); // 다음 원소에 대해 부분집합 생성
        select[idx] = false; // 현재 원소를 선택하지 않음
        subset(idx + 1); // 다음 원소에 대해 부분집합 생성
    }
}

• 첫 번째 호출 : subset(0)이 호출되면, idx는 0으로 초기화되고, select 배열의 첫 번째 원소를 선택하거나 선택하지 않는 두 가지 경우를 고려한다.
• 중첩 호출 : subset(idx + 1)이 호출되면 idx가 증가하고, 다음 원소에 대해 부분집합을 생성한다. 각 경우에 대해 선택 여부를 고려하여 재귀적으로 탐색한다.
• 기본 상태 도달 : idx가 N에 도달하면, 모든 원소에 대해 선택 여부가 결정되었으므로 현재 select 배열의 상태를 출력한다.

 

결론

재귀 호출을 활용한 부분집합 생성은 각 원소에 대해 선택 여부를 결정하는 간단하고 효과적인 방법이다. 재귀를 통해 모든 가능한 부분집합을 탐색할 수 있으며, 이 방식은 알고리즘의 직관적인 이해를 돕고 구현을 용이하게 한다. 하지만 시간 복잡도가 O(2^N)으로 매우 커지므로, 큰 N에 대해서는 성능을 고려한 최적화를 고려해 볼 필요가 있겠다.

 

 

비슷한 유형의 알고리즘들도 같이 정리해 보았다.

2024.07.30 - [ALGORITHM/알고리즘 이론] - [알고리즘] 순열(Permutation)

[알고리즘] 순열(Permutation)

2024.07.30 - [ALGORITHM/알고리즘 이론] - [알고리즘] 조합(Combination)

[알고리즘] 조합(Combination)