리스트에 담긴 정수들로 만들 수 있는 모든 부분 집합(subset)을 구할 때는 객체 지향 방식으로 클래스를 정의하는 것이 효과적입니다. 클래스 안에 필요한 속성과 메서드를 정의하고, 인스턴스를 생성해 기능을 호출하면 깔끔하게 문제를 해결할 수 있습니다.
아래는 이를 구현한 예제입니다.
예제 코드
class get_subset:
def sort_list(self, my_list):
return self.subset_find([], sorted(my_list))
def subset_find(self, curr, my_list):
if my_list:
return self.subset_find(curr, my_list[1:]) + self.subset_find(curr + [my_list[0]], my_list[1:])
return [curr]
my_list = []
num_elem = int(input("리스트의 원소 개수를 입력하세요 : "))
for i in range(0, num_elem):
elem = int(input("원소를 입력하세요 : "))
my_list.append(elem)
print("리스트의 부분 집합은 다음과 같습니다 : ")
print(get_subset().sort_list(my_list))
실행 결과
리스트의 원소 개수를 입력하세요 : 3
원소를 입력하세요 : 45
원소를 입력하세요 : 12
원소를 입력하세요 : 67
리스트의 부분 집합은 다음과 같습니다 :
[[], [67], [45], [45, 67], [12], [12, 67], [12, 45], [12, 45, 67]]
코드 설명
- 'get_subset'이라는 이름의 클래스를 정의하며, 내부에 'sort_list'와 'subset_find' 두 개의 메서드를 포함합니다.
- 'sort_list'는 입력받은 리스트를
sorted()함수로 오름차순 정렬한 뒤, 'subset_find'를 호출해 부분 집합 생성을 시작합니다. - 'subset_find'는 재귀적으로 동작하며, 각 원소를 현재 부분 집합에 포함하는 경우와 포함하지 않는 경우를 모두 탐색합니다.
- 사용자로부터 원소 개수와 각 원소 값을 입력받아 리스트를 구성합니다.
- 클래스의 인스턴스를 생성해 'sort_list' 메서드를 호출하고, 그 결과를 콘솔에 출력합니다.
재귀 동작 원리
'subset_find' 메서드는 각 호출 단계에서 리스트의 첫 번째 원소를 기준으로 두 가지 경우로 나누어 탐색합니다. 하나는 해당 원소를 현재 부분 집합(curr)에 추가하는 경우이고, 다른 하나는 추가하지 않고 건너뛰는 경우입니다. 입력 리스트가 빈 리스트가 되면 지금까지 누적된 curr를 결과 목록에 포함시킵니다.
이러한 방식으로 n개의 원소를 가진 리스트는 총 2ⁿ개의 부분 집합(공집합 포함)을 가지게 되며, 위 예제에서 3개의 원소로 8개의 부분 집합이 출력된 것을 확인할 수 있습니다. 시간 복잡도는 O(n × 2ⁿ)이므로, 원소 개수가 많아지면 실행 시간이 급격히 늘어난다는 점을 유의해야 합니다.