백트래킹_부분 집합 생성 (Subset Generation)

부분 집합 생성(Subset Generation)은 주어진 집합의 모든 부분 집합을 구하는 문제이다.

 

부분 집합(Subset) 생성의 개념

주어진 집합이 있을 때, 그 집합의 부분 집합이란 주어진 원소들 중 일부 또는 전체를 선택한 새로운 집합을 말한다. 부분 집합에는 빈 집합과 전체 집합도 포함된다. 주어진 집합에 포함된 원소의 개수가 n개라면, 그 집합의 부분 집합의 개수는 2^n개이다. 이는 각 원소를 선택하거나 선택하지 않음으로써 발생하는 모든 경우의 수이다.

예시

주어진 집합이 {1, 2, 3}이라고 할 때, 부분 집합은 다음과 같다:

[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

백트래킹을 사용한 부분 집합 생성

백트래킹(Backtracking)은 모든 가능한 선택을 시도하면서, 선택이 불가능하거나 더 이상 유효하지 않은 경로는 빠르게 되돌아가(백트랙) 탐색을 멈추는 방법이다. 부분 집합 생성에서는 각 원소에 대해 포함할지 여부를 선택하는 문제로, 이때 백트래킹이 매우 유용하다.

백트래킹을 사용하면 재귀적 방식으로 현재 상태에서 부분 집합을 점차 확장해 나가면서, 각 부분 집합을 완성할 수 있다. 이를 통해 불필요한 탐색을 줄이면서도 모든 경우의 수를 탐색할 수 있다.

 

부분 집합 생성 과정 (백트래킹)

백트래킹을 사용한 부분 집합 생성은 다음과 같은 순서로 진행된다:

1. 시작점 설정: 집합의 첫 번째 원소부터 부분 집합을 만들기 시작한다. 부분 집합은 빈 집합([])에서 시작한다.
2. 재귀적 탐색:
   • 현재 원소를 포함하거나 포함하지 않는 두 가지 선택을 하고, 그 선택에 따라 재귀적으로 다음 원소에 대한 탐색을 이어간다.
   • 각 재귀 호출은 현재까지 선택된 부분 집합을 기록하고, 다음 원소에 대해 동일한 방식으로 처리한다.
3. 기저 조건:
   • 모든 원소에 대해 선택이 완료되면(즉, 더 이상 탐색할 원소가 없으면), 해당 경로에서 만든 부분 집합을 결과로 저장한다.
4. 백트래킹:
   • 재귀 호출이 끝나면, 이전 선택을 되돌리기 위해 마지막 선택을 취소하고 다른 경로를 탐색한다. 이렇게 함으로써 탐색 범위를 줄일 수 있다.

 

백트래킹을 사용한 부분 집합 생성 구현

def generate_subsets(nums):
    def backtrack(start, current_subset):
        # 현재까지 만든 부분 집합을 결과에 추가
        result.append(list(current_subset))

        # start부터 끝까지 모든 요소를 확인
        for i in range(start, len(nums)):
            # 현재 요소를 부분 집합에 추가
            current_subset.append(nums[i])
            # 재귀적으로 다음 원소에 대해 백트래킹
            backtrack(i + 1, current_subset)
            # 백트래킹: 원래 상태로 되돌리기 위해 마지막 요소 제거
            current_subset.pop()

    result = []
    backtrack(0, [])  # 0번째 원소부터 탐색 시작, 빈 부분 집합에서 시작
    return result

# 테스트
nums = [1, 2, 3]
print(generate_subsets(nums))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

코드 설명:

1. generate_subsets(nums) 함수:
   • 입력 리스트 nums의 모든 부분 집합을 생성하는 함수이다. 결과를 담을 리스트 result를 선언하고, 재귀적으로 부분 집합을 생성하는 backtrack 함수가 호출된다.
2. backtrack(start, current_subset) 함수:
   • 이 함수는 부분 집합을 재귀적으로 생성하는 백트래킹 핵심 함수이다.
   • current_subset는 현재까지 선택된 부분 집합을 저장하는 리스트이다.
   • start는 현재 탐색할 리스트의 인덱스를 나타낸다. 처음엔 0부터 시작하며, 원소를 추가할 때마다 start 인덱스를 1씩 증가시키며 재귀적으로 호출한다.
3. 부분 집합 저장:
   • 현재까지 선택된 원소들이 담긴 current_subset을 결과 리스트에 저장한다.
4. 재귀 호출:
   • 각 원소에 대해 선택하거나 선택하지 않는 두 가지 선택을 진행한다. 현재 원소를 선택한 후 다음 재귀 호출에서 탐색을 이어가며, 탐색이 끝난 후에는 백트래킹을 위해 마지막으로 추가된 원소를 제거하고, 다시 다음 경로를 탐색한다.

 

백트래킹 부분 집합 생성의 동작 흐름

주어진 집합이 [1, 2, 3]일 때, 백트래킹의 동작 흐름은 다음과 같다:

1. 처음에는 빈 부분 집합([])으로 시작한다.
2. 첫 번째 원소 1을 선택하거나 선택하지 않는 두 가지 경우로 나뉜다:
   • [] → 원소 1을 포함하여 [1]로 확장하거나,
   • [1] → 더 확장하지 않고 그대로 나둔다.
3. 원소 1을 선택한 경우, 그다음 원소 2를 선택하거나 선택하지 않는 두 가지 경우로 나뉜다:
   • [1] → [1, 2]로 확장하거나,
   • [1] → 그대로 [1]을 유지한다.
4. 이 과정을 반복하여 모든 가능한 선택지를 탐색한다.

 

부분 집합 생성의 시간 복잡도

백트래킹을 사용한 부분 집합 생성에서, 모든 원소에 대해 각 선택지를 고려하므로 모든 부분 집합을 생성해야 한다. 주어진 집합이 n개의 원소를 포함한다면, 모든 부분 집합의 개수는 2^n개이다. 따라서 시간 복잡도는 O(2^n)이다.

• 시간 복잡도: O(2^n)
• → 각 원소에 대해 선택하거나 선택하지 않는 2가지 경우가 있으므로, 총 2^n개의 부분 집합이 생성된다.
• 공간 복잡도: O(n) (재귀 깊이) → 재귀 호출의 깊이는 최대 n이므로, 스택의 최대 깊이는 O(n)이다. 생성된 부분 집합 자체는 결과로 저장되므로 별도로 고려된다.

 

백트래킹을 사용한 부분 집합 생성의 장점

1. 효율적인 탐색: 백트래킹을 통해 재귀적 방식으로 모든 부분 집합을 효율적으로 생성할 수 있다. 각 선택지를 재귀적으로 탐색하면서, 불필요한 탐색은 빠르게 가지치기하여 효율성을 높인다.
2. 간결한 구현: 재귀적 호출을 통해 부분 집합을 탐색하는 방식이 직관적이며, 부분 집합 생성 문제를 간결하게 해결할 수 있다.
3. 다른 문제에도 확장 가능: 백트래킹 방식은 부분 집합 생성 외에도 조합, 순열, 그래프 탐색 등 다양한 문제에 응용될 수 있다.

• 부분 집합 생성은 주어진 집합의 모든 부분 집합을 구하는 문제입니다. 원소가 n개일 때, 총 2^n개의 부분 집합이 존재한다.
• 백트래킹은 각 원소를 포함하거나 포함하지 않음으로써 재귀적으로 부분 집합을 생성하는 알고리즘이다.
• 재귀 호출을 통해 부분 집합을 하나씩 확장해 나가며, 탐색이 끝나면 백트래킹(되돌림)을 통해 다른 경로를 탐색한다.
• 시간 복잡도는 O(2^n)으로, 주어진 집합의 모든 부분 집합을 생성하는 데 필요한 복잡도이다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms